零钱兑换II

力扣 518. 零钱兑换 II

题目说明

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
提示：
- 0 <= amount (总金额) <= 5000
- 1 <= coin (硬币面额) <= 5000
- 硬币种类不超过 500 种
- 结果符合 32 位符号整数

示例

示例 1:

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2:

1
2
3

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。

示例 3:

1 2	输入: amount = 10, coins = [10] 输出: 1

笔者理解

此题是一道动态规划算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题很直接的动态规划题，想清楚状态转移就很清晰了，让我们来看看具体如何实现的吧。

实现

class Solution {
    /*
     * 动态规划
     * 状态转移方程
     */
    public int change(int amount, int[] coins) {
        int dp[] = new int[amount+1];

        // 设置起始状态
        dp[0] = 1;
        
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                // 当前面值j的可能组成等于
                // 所有j - coin[i]的可能性累加而来
                // 比如：
                // amount = 5, coins = [1, 2, 5]
                // dp[1] += dp[0]   1   {{1}}
                // dp[2] += dp[1]   1   {{1,1}}
                // dp[3] += dp[2]   1   {{1,1,1}}
                // dp[4] += dp[3]   1   {{1,1,1,1}}
                // dp[5] += dp[4]   1   {{1,1,1,1,1}}
                //--------------------
                // dp[2] += dp[0]   2   {{1,1},{2}}
                // dp[3] += dp[1]   2   {{1,1,1},{2,1}}
                // dp[4] += dp[2]   3   {{1,1,1,1},{2,1,1},{2,2}}
                // dp[5] += dp[3]   3   {{1,1,1,1,1},{2,1,1,1},{2,2,1}}
                //--------------------
                // dp[5] += dp[0]   4   {{1,1,1,1,1},{2,1,1,1},{2,2,1},{5}}
                dp[j] += dp[j - coins[i]];
            }
        }
        
        return dp[amount];
    }
}