完全背包理論基礎(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];
}
}