518. 零钱兑换II

完全背包

class Solution {
    public int change(int amount, int[] coins) {

        /**
         * dp[j]定义为总金额为j时组合的方式数量
         * 初始dp[0] == 1
         */
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        /**
         * 完全背包中，每个数字可以重复使用
         * 因此内循环要从小到大遍历
         * 对于求组合数，dp[j] （考虑coins[i]的组合总和） 就是所有的dp[j - coins[i]]（不考虑coins[i]）相加
         * 如果求组合数就是外层for循环遍历物品，内层for遍历背包
         * 如果求排列数就是外层for遍历背包，内层for循环遍历物品
         */
        for (int i = 1; i <= coins.length; i++) {

            for (int j = coins[i - 1]; j <= amount; j++) {
                dp[j] += dp[j - coins[i - 1]];
            }
        }

        return dp[amount];
    }
}

/**
 * 时间复杂度 O(amount*n)
 * 空间复杂度 O(amount)
 */

https://leetcode-cn.com/problems/coin-change-2/