题目描述

解题思路

• 确定dp数组以及下标的含义

dp[j]：凑成总金额j的货币组合数为dp[j]

• 确定递推公式

dp[j] （考虑coins[i]的组合总和） 就是所有的dp[j - coins[i]]（不考虑coins[i]）相加。
所以递推公式：dp[j] += dp[j - coins[i]];
也就是求多少种组合的方式，常见的递推公式。

• dp数组如何初始化

dp[0]初始化为1，递归的基础。凑成0的方法也只有一种。

• 确定遍历顺序

由递推公式可得从前向后遍历。
但是此时背包和物品的遍历顺序有讲究！！！
此问题是多重背包的组合问题，所以应该先便利物品。例如：coins[0] = 1，coins[1] = 5。
那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。

• 举例推导dp数组

输入: amount = 5, coins = [1, 2, 5] ，dp状态图如下：

/**
         * 完全背包问题
         *
         * @param amount
         * @param coins
         * @return
         */
public int change(int amount, int[] coins) {
    // dp[j]：凑成总金额j的货币组合数为dp[j]
    int[] dp = new int[amount + 1];
    dp[0] = 1;  // 初始化为0，表示0也有一种方法
    // 由于求的是组合，部分顺序，所以应该先遍历物品，防止顺序问题
    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];
}