1、前言

題目描述

2、思路

本題使用完全背包的思路，那完全背包跟 0-1 背包有何區(qū)別呢？

0-1 限制了物品的數(shù)量，物品并不是無限的。假設(shè)有物品 weight 跟物品的價(jià)值 value，weight_i 表示每個(gè)物品的重量，value_i 表示每個(gè)物品對應(yīng)的價(jià)值，在不超過背包容量的情況下怎樣才能使得價(jià)值最大？其實(shí)對于每個(gè)物品來說，都可以放與不放。那么定義一個(gè)二位數(shù)組 dp[i][j] 表示在選擇物品 i 、背包容量為 j 的情況下價(jià)值最大。

那么對于 dp[i][j] 來說，存在放第 i 個(gè)物品跟不放第 i 個(gè)物品。

在不放第 i 個(gè)物品的情況下，直接繼承上一個(gè)背包的數(shù)據(jù)情況，即 dp[i][j] = dp[i - 1][j]。

在放第 i 個(gè)物品的情況下，那么需要加上第 i 個(gè)物品的價(jià)值 value_i[i - 1]（數(shù)組從 0開始），然后需要加上去掉 i 的重量的情況下，應(yīng)該由哪個(gè)數(shù)據(jù)推導(dǎo)過來，即 dp[i - 1][j - weight_i[i - 1]]，所以 dp[i][j] = dp[i - 1][j - weight_i[i - 1]] + value_i[i - 1]。

所以最大價(jià)值為 dp[i][j] = max {dp[i - 1][j], dp[i - 1][j - weight_i[i - 1]] + value_i[i - 1]}

要牢牢記住一點(diǎn)，動(dòng)態(tài)規(guī)劃是自底向上，由已知推到未知。

那么對應(yīng)完全背包來說，物品的數(shù)量是無限的，那么也存在上面放與不放的情況。
針對這題，針對物品 i，存在放0個(gè)，放1個(gè)，放 k 個(gè)，所以 dp[i][j] = dp[i - 1][j - 0 * coins[i]] + dp[i - 1][j - 1 * coins[i]] ....，而 dp[i][j - coins[i]] = dp[i][j - coins[i] - 0 * coins[i]] + dp[i][j - coins[i] - 1 * coins[i]] + ...。

那么，上面兩式相減得：dp[i][j]?dp[i][j?coins[i]]=dp[i?1][j]，即 dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]

3、代碼

初始代碼：

public class Solution {

    public int change(int amount, int[] coins) {
        int len = coins.length;
        if (len == 0) {
            if (amount == 0) {
                return 1;
            }
            return 0;
        }

        int[][] dp = new int[len][amount + 1];
        // 題解中有說明應(yīng)該如何理解這個(gè)初始化
        dp[0][0] = 1;

        // 填第 1 行
        for (int i = coins[0]; i <= amount; i += coins[0]) {
            dp[0][i] = 1;
        }

        for (int i = 1; i < len; i++) {
            for (int j = 0; j <= amount; j++) {
                for (int k = 0; j - k * coins[i] >= 0; k++) {
                    dp[i][j] += dp[i - 1][j - k * coins[i]];
                }
            }
        }
        return dp[len - 1][amount];
    }
}

優(yōu)化后代碼：

class Solution {
    public int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length + 1][amount + 1];
        for (int i = 0; i < dp.length; i++) {
            // 沒有 amount 時(shí)，不用湊數(shù)，直接得1
            // dp[0][i] 為 0，但是數(shù)組默認(rèn)都是0，所以不用寫
            dp[i][0] = 1;
        }

        for(int i = 1; i <= coins.length; i++){
            for(int j = 1; j <= amount; j++){
                if(j - coins[i - 1] < 0){
                    dp[i][j] = dp[i - 1][j];
                }else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
                }
            }
        }

        return dp[coins.length][amount];
    }
}