完全背包理論基礎(chǔ)
文字講解：完全背包理論基礎(chǔ)
有N件物品和一個(gè)最多能背重量為W的背包南片。第i件物品的重量是weight[i]互例，得到的價(jià)值是value[i] 。每件物品都有無(wú)限個(gè)（也就是可以放入背包多次）磺平，求解將哪些物品裝入背包里物品價(jià)值總和最大。
完全背包和01背包問(wèn)題唯一不同的地方就是捉貌，每種物品有無(wú)限件昔穴。因此要正序遍歷，從小到大剧蚣。
純完全背包遍歷順序無(wú)所謂支竹，但是具體題目可能有改動(dòng)。
518.零錢(qián)兌換II
題目鏈接/文字講解：零錢(qián)兌換II
題設(shè)：給你一個(gè)整數(shù)數(shù)組 coins 表示不同面額的硬幣鸠按，另給一個(gè)整數(shù) amount 表示總金額礼搁。
請(qǐng)你計(jì)算并返回可以湊成總金額的硬幣組合數(shù)。如果任何硬幣組合都無(wú)法湊出總金額目尖，返回 0 馒吴。假設(shè)每一種面額的硬幣有無(wú)限個(gè)。
題目數(shù)據(jù)保證結(jié)果符合 32 位帶符號(hào)整數(shù)瑟曲。
思路：動(dòng)規(guī)五部曲：
1.確定dp數(shù)組以及下標(biāo)的含義-dp[j]：湊成總金額j的貨幣組合數(shù)為dp[j]饮戳。
2.確定遞推公式-dp[j] 就是所有的dp[j - coins[i]]（考慮coins[i]的情況）相加。所以遞推公式：dp[j] += dp[j - coins[i]]洞拨。
3.初始化：dp[0]初始為1扯罐，其他全部初始為0。
4.遍歷順序：外物品烦衣，內(nèi)背包歹河，才能保證是組合而不是排列齿椅。
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];
}
}
377. 組合總和 Ⅳ
視頻鏈接/文字講解：組合總和 Ⅳ
視頻講解：
題設(shè)：給你一個(gè)由 不同 整數(shù)組成的數(shù)組 nums ，和一個(gè)目標(biāo)整數(shù) target 启泣。請(qǐng)你從 nums 中找出并返回總和為 target 的元素組合的個(gè)數(shù)涣脚。順序不同的序列被視作不同的組合。
思路：上題換了個(gè)形式寥茫，從組合變?yōu)榱伺帕星彩础?dòng)規(guī)五部曲：
1.dp數(shù)組含義：湊成target的排列數(shù)有dp[target]個(gè)。
2.遞歸表達(dá)式：dp[j] += dp[j - nums[i]]纱耻。
3.數(shù)組初始化：dp[0]為1芭梯，其他為0。
4.遍歷順序：外背包弄喘，里物品玖喘，順序遍歷，nums下標(biāo)從小到大蘑志。
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int j = 0; j <= target; j++) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= j) dp[j] += dp[j - nums[i]];
}
}
return dp[target];
}
}
