面试题 08.11. 硬币 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    private static final int PRIME = 1000000007;
    private static final int[] COINS = new int[]{25, 10, 5, 1};

    public int waysToChange(int n) {
        // 定义 dp[i] 为 i 有多少种表示法
        int[] dp = new int[n + 1];
        dp[0] = 1;
        
        for (int coin : COINS) {
            for (int i = 1; i <= n; i++) {
                if (i - coin >= 0) {
                    dp[i] += dp[i - coin];
                    dp[i] %= PRIME;
                }
            }
        }

        return dp[n];
    }
}

注意此题是求的组合数量而不是排列数量，比如总金额 6 只存在 1+1+1+1+1+1 与 1+5 两种组合，那么此时需要在外层遍历硬币，以避免出现重复的组合，如：1+5 与 5+1 其实属于同一种组合，只应该出现一次。

References

面试题 08.11. 硬币