image.png

解法

public static int change(int amount, int[] coins) {
        // dp数组代表amount为j时，有几种组合方式
        int[] dp = new int[amount + 1];
        // amount为0时，有1种
        dp[0] = 1;
        // 先遍历物品，再遍历容量,这样物品顺序固定，计算的是组合数，而不是排列数
        // 先遍历容量，再遍历物品，会是排列的感觉，因为每个容量下，都从头取物品，
        // 以3为例，会出现遍历1的时候，先拿2的组合数加上去，然后遍历2的时候，再拿1
        // 的组合数加上去，就是排列了。
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                // 状态转移，不取coins[i],加上取coins[i]的组合数
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }