有砝码 1g,2g,3g...100g,组成 100g 的重量有几种方式?
这道题应该可以用动态规划做,但一下子没想出来(太渣了)
写了一个回溯的算法,但效率太差了:
function counterweightWays(currentNum, allNum, leftWeight, tmpResult, result) {
if (currentNum > allNum) {
return }
if (leftWeight == 0) {
result.push(Array.from(tmpResult))
return
}
const maxNum = Math.floor(leftWeight / currentNum)
for (let n = maxNum; n >= 0; n--) {
tmpResult.push(n)
counterweightWays(currentNum + 1, allNum, leftWeight - n * currentNum, tmpResult, result)
tmpResult.pop()
}
}
1
jmc891205 2020-09-06 21:24:25 +08:00 via iPhone
搜索一下零钱兑换问题
|
2
fishCatcher 2020-09-06 21:53:57 +08:00 1
// 设 dp[i]是组成 i 克的方法个数, 1 <= i <= n
for (int i = 1; i <= n; i++) dp[i] = 1; // base case,直接拿 1 个 i 克的砝码即可 for (int i = 2; i <= n; i++) for (int j = 1; j <= i / 2; j++) dp[i] += dp[j] * dp[i - j]; return dp[n]; |
3
zhy0216 2020-09-06 21:55:15 +08:00
|
4
salamanderMH OP |
5
salamanderMH OP @zhy0216 哇,太强了。
|