一道算法题，请教一下

[salamanderMH]

问题

有砝码 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()    
    }
}

[jmc891205]

搜索一下零钱兑换问题

[fishCatcher]

// 设 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];

[zhy0216]

https://raw.githubusercontent.com/tianyicui/pack/master/V2.pdf

[salamanderMH]

@jmc891205 看到原题了，https://www.cnblogs.com/grandyang/p/7669088.html
谢谢

[salamanderMH]

@zhy0216 哇，太强了。