[数据结构与算法]518. 零钱兑换 II

思路

该题目是一个组合问题。

动规五部曲

1.定义dp数组

dp数组：dp[i]为当前amount=i时，一共有dp[i]种方法。

2.递推公式

因为该题为组合问题，所以dp[j]+=dp[j-coins[i]]。

当i为5的时候

• 已经有一个1（coins[i]） 的话，有 dp[4]种方法 凑成 dp[5]。
• 已经有一个2（coins[i]） 的话，有 dp[3]种方法 凑成 dp[5]。
• 已经有一个3（coins[i]） 的话，有 dp[2]中方法 凑成 dp[5]
• 已经有一个4（coins[i]） 的话，有 dp[1]中方法 凑成 dp[5]
• 已经有一个5 （coins[i]）的话，有 dp[0]中方法 凑成 dp[5]

那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - coins[i]] 累加起来。

3.dp数组初始化

根据dp数组的含义可以知道dp[0]=1;

4.遍历顺序

根据递推公式可以知道要正序遍历。但是因为该物品可以重复放入，所以内层也是正序遍历。

5.打印dp数组

dp数组最后一个元素就是结果。

代码

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