[数据结构与算法]完全背包中等 LeetCode518. 零钱兑换 II

518. 零钱兑换 II

描述

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。

分析

完全背包问题
dp[i]： 凑出i的所有组合数
动态转移方程： dp[j] += dp[j - coins[i]];
动态转移方程有两种情况：1.凑出i的组合不包括当前数，则继承上一步的结果dp[j]；2.凑出i的组合数包括当前数dp[j-nums[j]]。因为是求个数，所以应该把两个情况加起来。
初始化： 因为是计算数量的问题，所以dp[0]初始化应该是1，这样方便计算次数。

注意！与01背包相反，内层循环需要从前往后便利，这样才能利用当前数在前面已经遍历的结果。

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++){
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}