凑钱方法数 - 动态规划解题

输入样例 4 10 1 2 5 10 5 3 2 1

输出样例 11

说明 小珅可以用面值为1的钱币凑出10，也可以用面值为2的钱币凑出10，依此类推，共有11种凑法。

提示 可以使用动态规划来解决这个问题。设dp[i][j]表示使用前i种面值的钱币凑出金额j的方法数。那么对于第i种面值的钱币，有两种情况：不使用这种面值的钱币，那么dp[i][j] = dp[i-1][j]；使用至少一枚这种面值的钱币，那么dp[i][j] = dp[i][j-wi] + dp[i-1][j]。最终的答案为dp[n][m]。