leetcode面试题 08.11. 硬币

硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

示例1:
输入: n = 5
输出：2
解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1

示例2:
输入: n = 10
输出：4
解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1

说明：
注意:
你可以假设：
0 <= n (总金额) <= 1000000

这道题很容易就能看出来是一个背包问题。每个物品有无限个，怎么放进去背包。但也很容易写出错误代码。
比如下面这种：

错误示范

1
2
3
4
5
6

for(int i = 1; i <= n; i++) {
           for(int coin: coins) {
               if(i - coin < 0) break;
               dp[i] = (dp[i] + dp[i - coin]) % 1000000007;
           }
       }

先遍历数字情况，在遍历硬币，这么做会有一个问题：
假设我们有1元和5元硬币。当我们需要组合出7元时候，这个程序会把（2+5）和（5+2）算成两种，也就是说这么没办法解决方案的顺序问题。

正确写法

正确的方法应该是先遍历硬币，回想背包问题，我们无论哪种背包，都是在最外层先遍历每个物品的，内层是背包容量。
在最外层遍历硬币，可以保证之后的硬币不会再用到之前的硬币，这么就不会重复了。

1
2
3
4
5
6
7
8
9
10
11
12

public int waysToChange(int n) {
        int mod = 1000000007;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        int[] coins = {1, 5, 10, 25};
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= n; j++) {
                dp[j] = (dp[j] + dp[j - coins[i]]) % mod;
            }
        }
        return dp[n];
    }

leetcode 86/100