力扣AC：零钱兑换II - 动态规划

题目链接

零钱兑换II

题目描述

实现代码

动态规划思想：记dp[i]表示使用coins数组组合金额i的组合次数，本来是一个简单的动态规划思想，不过问题就在于循环遍历的顺序，该题跟背包问题类似，我们考虑如下两种遍历顺序的区别：

1. 先金额后零钱：这是一个排列问题，比如我们先选了金额3，然后在coins中如果有1和2，就会出现先选1后选2 和 先选2后选1 两种情况相加，而对于本题来说这两种情况是一样的；
2. 先零钱后金额：这是一个组合问题，我们可以首先确定选择的零钱的顺序，比如我们先选了1，然后剩下了amout-1的零钱，这样就相当于对每个位置进行逐一确定，同时前面确定的零钱也会影响后面确定的值；即此时可以将 先选1后选2 和 先选2后选1 看成是一种情况；

实现代码如下：

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}