背包問題
- 判斷是排列問題 還是 組合問題
- 確定遍歷順序：
- 如果求組合數(shù)就是外層for循環(huán)遍歷物品，內(nèi)層for遍歷背包惠勒。
- 如果求排列數(shù)就是外層for遍歷背包赚抡，內(nèi)層for循環(huán)遍歷物品。
解釋：如果把遍歷nums（物品）放在外循環(huán)纠屋，遍歷target的作為內(nèi)循環(huán)的話涂臣，舉一個(gè)例子：計(jì)算dp[4]的時(shí)候，結(jié)果集只有 {1,3} 這樣的集合售担，不會(huì)有{3,1}這樣的集合赁遗，因?yàn)閚ums遍歷放在外層，3只能出現(xiàn)在1后面族铆！
https://leetcode-cn.com/problems/coin-change/solution/yi-pian-wen-zhang-chi-tou-bei-bao-wen-ti-sq9n/
背包問題力扣完整攻略
只要按如下順序刷題岩四，相信會(huì)幫你在學(xué)習(xí)背包問題的路上少走很多彎路！
「力扣」上的 0-1 背包問題
416.分割等和子集
474.一和零
494.目標(biāo)和
879 ：盈利計(jì)劃（困難）
1049.最后一塊石頭的重量 II
「力扣」上的 完全背包問題：
- 零錢兌換 II
377.組合總和Ⅳ. !!不是「完全背包」問題
70.爬樓梯進(jìn)階版 - 零錢兌換
279.完全平方數(shù)
139.單詞拆分
第 1449 題：數(shù)位成本和為目標(biāo)值的最大數(shù)字（困難）
「力扣」上的 多重背包問題：
1. 416.分割等和子集
給你一個(gè) 只包含正整數(shù) 的 非空 數(shù)組 nums 哥攘。請(qǐng)你判斷是否可以將這個(gè)數(shù)組分割成兩個(gè)子集剖煌，使得兩個(gè)子集的元素和相等。
示例 1：
輸入：nums = [1,5,11,5]
輸出：true
解釋：數(shù)組可以分割成 [1, 5, 5] 和 [11] 逝淹。
【0-1背包存在性問題：是否存在一個(gè)子集,其和為target=sum/2,外循環(huán)nums,內(nèi)循環(huán)target倒序】
public class Solution {
public boolean canPartition(int[] nums) {
int len = nums.length;
int sum = 0;
for (int num : nums) {
sum += num;
}
if ((sum & 1) == 1) {
return false;
}
int target = sum / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
if (nums[0] <= target) {
dp[nums[0]] = true;
}
for (int i = 1; i < len; i++) {
for (int j = target; nums[i] <= j; j--) {
if (dp[target]) {
return true;
}
dp[j] = dp[j] || dp[j - nums[i]];
}
}
return dp[target];
}
}
//時(shí)間復(fù)雜度：O(NC)O(NC)：這里 NN 是數(shù)組元素的個(gè)數(shù)末捣，CC 是數(shù)組元素的和的一半；
//空間復(fù)雜度：O(C)O(C)：減少了物品那個(gè)維度创橄，無論來多少個(gè)數(shù)箩做，用一行表示狀態(tài)就夠了。
2. 474. 給你一個(gè)二進(jìn)制字符串?dāng)?shù)組 strs 和兩個(gè)整數(shù) m 和 n 妥畏。
請(qǐng)你找出并返回 strs 的最大子集的長(zhǎng)度邦邦，該子集中 最多 有 m 個(gè) 0 和 n 個(gè) 1 安吁。
如果 x 的所有元素也是 y 的元素击蹲，集合 x 是集合 y 的 子集 逞壁。
示例 1：
輸入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
輸出：4
解釋：最多有 5 個(gè) 0 和 3 個(gè) 1 的最大子集是 {"10","0001","1","0"} 挟鸠，因此答案是 4 缭嫡。
其他滿足題意但較小的子集包括 {"0001","1"} 和 {"10","1","0"} 钓觉。{"111001"} 不滿足題意犁罩，因?yàn)樗?4 個(gè) 1 拙友，大于 n 的值 3 辟癌。
解析：
通常與「背包問題」相關(guān)的題考察的是 將原問題轉(zhuǎn)換為「背包問題」的能力氏身。
要將原問題轉(zhuǎn)換為「背包問題」巍棱，往往需要從題目中抽象出「價(jià)值」與「成本」的概念。
這道題如果抽象成「背包問題」的話蛋欣，應(yīng)該是：
每個(gè)字符串的價(jià)值都是 1（對(duì)答案的貢獻(xiàn)都是 1）航徙，選擇的成本是該字符串中 1 的數(shù)量和 0 的數(shù)量。
以上是原始狀態(tài)轉(zhuǎn)義公式陷虎，下面代碼是經(jīng)過空間優(yōu)化后的：
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int len = strs.length;
int[][] cnt = new int[len][2];
for (int i = 0; i < len; i++) {
int zero = 0, one = 0;
for (char c : strs[i].toCharArray()) {
if (c == '0') zero++;
else one++;
}
cnt[i] = new int[]{zero, one};
}
int[][] f = new int[m + 1][n + 1];
for (int k = 0; k < len; k++) {
int zero = cnt[k][0], one = cnt[k][1];
for (int i = m; i >= zero; i--) {
for (int j = n; j >= one; j--) {
f[i][j] = Math.max(f[i][j], f[i - zero][j - one] + 1);
}
}
}
return f[m][n];
}
}
時(shí)間復(fù)雜度：O(k?m?n)
空間復(fù)雜度：O(m * n)
3. 494 目標(biāo)和
給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) target 到踏。
向數(shù)組中的每個(gè)整數(shù)前添加 '+' 或 '-' ，然后串聯(lián)起所有整數(shù)尚猿，可以構(gòu)造一個(gè) 表達(dá)式 ：
例如窝稿，nums = [2, 1] ，可以在 2 之前添加 '+' 凿掂，在 1 之前添加 '-' 讹躯，然后串聯(lián)起來得到表達(dá)式 "+2-1" 。
返回可以通過上述方法構(gòu)造的缠劝、運(yùn)算結(jié)果等于 target 的不同 表達(dá)式 的數(shù)目潮梯。
示例 1：
輸入：nums = [1,1,1,1,1], target = 3
輸出：5
解釋：一共有 5 種方法讓最終目標(biāo)和為 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
解析：
【0-1背包不考慮元素順序的組合問題】
當(dāng)使用遞推形式時(shí)惨恭，我們通常會(huì)使用「靜態(tài)數(shù)組」來存儲(chǔ)動(dòng)規(guī)值秉馏，因此還需要考慮維度范圍的：
第一維為物品數(shù)量：范圍為 nums 數(shù)組長(zhǎng)度
第二維為中間結(jié)果：令 s 為所有 nums 元素的總和（題目給定了 nums[i] 為非負(fù)數(shù)的條件，否則需要對(duì) nums[i] 取絕對(duì)值再累加）脱羡，那么中間結(jié)果的范圍為 [-s, s]
class Solution {
public int findTargetSumWays(int[] nums, int t) {
int n = nums.length;
int s = 0;
for (int i : nums) s += Math.abs(i);
if (Math.abs(t) > s) return 0;
int[][] f = new int[n + 1][2 * s + 1];
f[0][0 + s] = 1;
for (int i = 1; i <= n; i++) {
int x = nums[i - 1];
for (int j = -s; j <= s; j++) {
if ((j - x) + s >= 0) f[i][j + s] += f[i - 1][(j - x) + s];
if ((j + x) + s <= 2 * s) f[i][j + s] += f[i - 1][(j + x) + s];
}
}
return f[n][t + s];
}
}
4. 879. 盈利計(jì)劃
class Solution {
int mod = (int)1e9+7;
public int profitableSchemes(int n, int min, int[] gs, int[] ps) {
int m = gs.length;
long[][][] f = new long[m + 1][n + 1][min + 1];
for (int i = 0; i <= n; i++) f[0][i][0] = 1;
for (int i = 1; i <= m; i++) {
int a = gs[i - 1], b = ps[i - 1];
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= min; k++) {
f[i][j][k] = f[i - 1][j][k];
if (j >= a) {
int u = Math.max(k - b, 0);
f[i][j][k] += f[i - 1][j - a][u];
if (f[i][j][k] >= mod) f[i][j][k] -= mod;
}
}
}
}
return (int)f[m][n][min];
}
}
空間優(yōu)化版本：
class Solution {
int mod = (int)1e9+7;
public int profitableSchemes(int n, int min, int[] gs, int[] ps) {
int m = gs.length;
int[][] f = new int[n + 1][min + 1];
for (int i = 0; i <= n; i++) f[i][0] = 1;
for (int i = 1; i <= m; i++) {
int a = gs[i - 1], b = ps[i - 1];
for (int j = n; j >= a; j--) {
for (int k = min; k >= 0; k--) {
int u = Math.max(k - b, 0);
f[j][k] += f[j - a][u];
if (f[j][k] >= mod) f[j][k] -= mod;
}
}
}
return f[n][min];
}
}
5. 518. 零錢兌換II (Coin Change 2)
給你一個(gè)整數(shù)數(shù)組 coins 表示不同面額的硬幣萝究，另給一個(gè)整數(shù) amount 表示總金額。
請(qǐng)你計(jì)算并返回可以湊成總金額的硬幣組合數(shù)锉罐。如果任何硬幣組合都無法湊出總金額帆竹，返回 0 。
假設(shè)每一種面額的硬幣有無限個(gè)脓规。
題目數(shù)據(jù)保證結(jié)果符合 32 位帶符號(hào)整數(shù)栽连。
示例 1：
輸入：amount = 5, coins = [1, 2, 5]
輸出：4
解釋：有四種方式可以湊成總金額：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
解釋：完全背包問題
定義 f[i][j]為考慮前 ii 件物品，湊成總和為 j 的方案數(shù)量。
為了方便初始化秒紧，我們一般讓f[0][x] 代表不考慮任何物品的情況绢陌。
因此我們有顯而易見的初始化條件：f[0][0] = 1，其余 f[0][x] = 0熔恢。
代表當(dāng)沒有任何硬幣的時(shí)候脐湾，存在湊成總和為 0 的方案數(shù)量為 1；湊成其他總和的方案不存在叙淌。
【完全背包不考慮順序的組合問題】
class Solution {
public int change(int cnt, int[] cs) {
int n = cs.length;
int[] f = new int[cnt + 1];
f[0] = 1;
for (int i = 1; i <= n; i++) {
int val = cs[i - 1];
for (int j = val; j <= cnt; j++) {
f[j] += f[j - val];
}
}
return f[cnt];
}
}
6. 322. 零錢兌換
給你一個(gè)整數(shù)數(shù)組 coins 秤掌，表示不同面額的硬幣；以及一個(gè)整數(shù) amount 鹰霍，表示總金額闻鉴。
計(jì)算并返回可以湊成總金額所需的 最少的硬幣個(gè)數(shù) 。如果沒有任何一種硬幣組合能組成總金額衅谷，返回 -1 椒拗。
你可以認(rèn)為每種硬幣的數(shù)量是無限的似将。
示例 1：
輸入：coins = [1, 2, 5], amount = 11
輸出：3
解釋：11 = 5 + 5 + 1
【完全背包最值問題：外循環(huán)coins,內(nèi)循環(huán)amount正序】
int coinChange(vector<int> &coins, int amount)
{
vector<long long> dp(amount, INT_MAX); //給dp數(shù)組每個(gè)位置賦初值為INT_MAX是為了最后判斷是否能填滿amount,要用long long 類型
dp[0] = 0; //dp[i]:換到面值i所用的最小數(shù)量
for (int coin : coins)
{
for (int i = coin; i <= amount; i++)
{
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] == INT_MAX ? -1 : dp[amount];
}
7. 279. 完全平方數(shù)
給你一個(gè)整數(shù) n 获黔，返回和為 n 的完全平方數(shù)的 最少數(shù)量 。
完全平方數(shù) 是一個(gè)整數(shù)在验，其值等于另一個(gè)整數(shù)的平方玷氏；換句話說，其值等于一個(gè)整數(shù)自乘的積腋舌。例如盏触，1、4块饺、9 和 16 都是完全平方數(shù)赞辩，而 3 和 11 不是。
示例 1：
輸入：n = 12
輸出：3
解釋：12 = 4 + 4 + 4
完全背包的最值問題：完全平方數(shù)最小為1,最大為sqrt(n),故題目轉(zhuǎn)換為在nums=[1,2.....sqrt(n)]中選任意數(shù)平方和為target=n
外循環(huán)nums,內(nèi)循環(huán)target正序,應(yīng)用轉(zhuǎn)移方程1
int numSquares(int n)
{
vector<int> dp(n + 1, INT_MAX); //dp[i]:和為i的完全平方數(shù)的最小數(shù)量
dp[0] = 0;
for (int num = 1; num <= sqrt(n); num++)
{
for (int i = 0; i <= n; i++)
{
if (i >= num * num)
dp[i] = min(dp[i], dp[i - num * num] + 1);
}
}
return dp[n];
}
8. 377. 組合總和 Ⅳ
【完全背包問題的排列問題】在nums中任選一些數(shù),和為target
考慮順序的組合問題：外循環(huán)target,內(nèi)循環(huán)nums,應(yīng)用狀態(tài)方程3
示例 1：
輸入：nums = [1,2,3], target = 4
輸出：7
解釋：
所有可能的組合為：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
請(qǐng)注意授艰，順序不同的序列被視作不同的組合辨嗽。
int combinationSum4(vector<int> &nums, int target)
{
vector<int> dp(target + 1);
dp[0] = 1;
for (int i = 1; i <= target; i++)
{
for (int num : nums)
{
if (num <= i)
dp[i] += dp[i - num];
}
}
return dp[target];
}
9. 1155. 擲骰子的N種方法
投擲骰子的方法數(shù)：d個(gè)骰子,每個(gè)有f個(gè)面(點(diǎn)數(shù)為1,2,...f),求骰子點(diǎn)數(shù)和為target的方法
分組0/1背包的組合問題：dp[i][j]表示投擲i個(gè)骰子點(diǎn)數(shù)和為j的方法數(shù);三層循環(huán)：最外層為背包d,然后先遍歷target后遍歷點(diǎn)數(shù)f
應(yīng)用二維拓展的轉(zhuǎn)移方程3：dp[i][j]+=dp[i-1][j-f];
int numRollsToTarget(int d, int f, int target)
{
vector<vector<int>> dp(d + 1, vector<int>(target + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= d; i++)
for (int j = 1; j <= target; j++)
for (int k = 1; k <= f && j >= k; k++)
dp[i][j] += dp[i - 1][j - k];
return dp[d][target];
}
