百度免費(fèi)做網(wǎng)站友情鏈接格式
動態(tài)規(guī)劃題目中,常出現(xiàn)背包的相關(guān)問題,這里單獨(dú)挑出來訓(xùn)練
A.01背包
1.01背包模板題
【模板】01背包_牛客題霸_??途W(wǎng) (nowcoder.com)
你有一個背包,最多能容納的體積是V。
現(xiàn)在有n個物品,第i個物品的體積為𝑣𝑖vi??,價值為𝑤𝑖wi?。
(1)求這個背包至多能裝多大價值的物品?
(2)若背包恰好裝滿,求至多能裝多大價值的物品?
第一問
1.狀態(tài)表示:用dp[ i ][ j ]表示選到第 i 個物品, 體積不超過 j ,物品的最大價值
2.狀態(tài)轉(zhuǎn)移方程:dp[ i ][ j ] = max(dp[ i - 1 ][ j ], dp[ i - 1 ][ j - v[ i ] ] + w[ i ] )
3.初始化:無需初始化
4.填表順序:從上往下每一行
5.返回值:dp[ n?][ V?]
注意:由于 j - v[ i ] 可能小于0,所以需要提前特判
第二問
1.狀態(tài)表示:用dp[ i ][ j ]表示選到第 i 個物品, 體積恰好?j ,物品的最大價值
2.狀態(tài)轉(zhuǎn)移方程:dp[ i ][ j ] = max(dp[ i - 1 ][ j ], dp[ i - 1 ][ j - v[ i ] ] + w[ i ] )
3.初始化:根據(jù)題目初始化(見注意)
4.填表順序:從上往下每一行
5.返回值:dp[ n?][ V?]
注意:由于dp狀態(tài)表示地特殊性,可能存在無法使?fàn)顟B(tài)存在的情況,所以我們規(guī)定用 - 1 來表示狀態(tài)不存在,于是在 j >= 1使,dp[ 0 ][ j ] = -1,在打印值時,也需要提前特判
#include<iostream>
#include<vector>
#include<string.h>using namespace std;const int N = 1010;
int n, V, v[N], w[N];int dp[N][N];int main()
{cin >> n >> V;for(int i = 1; i <= n; ++i)cin >> v[i] >> w[i];for(int i = 1; i <= n; ++i)for(int j = 1; j <= V; ++j){dp[i][j] = dp[i - 1][j];if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);}cout << dp[n][V] << endl;memset(dp, 0, sizeof dp);for(int j = 1; j <= V; ++j) dp[0][j] = -1;for(int i = 1; i <= n; ++i)for(int j = 1; j <= V; ++j){dp[i][j] = dp[i - 1][j];if(j >= v[i] && dp[i - 1][j - v[i]] != -1) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);}cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;return 0;
}
這是二維ac代碼
#include<iostream>
#include<vector>
#include<string.h>using namespace std;const int N = 1010;
int n, V, v[N], w[N];int dp[N];int main()
{cin >> n >> V;for(int i = 1; i <= n; ++i)cin >> v[i] >> w[i];for(int i = 1; i <= n; ++i)for(int j = V; j >= v[i]; --j)dp[j] = max(dp[j], dp[j - v[i]] + w[i]);cout << dp[V] << endl;memset(dp, 0, sizeof dp);for(int j = 1; j <= V; ++j) dp[j] = -1;for(int i = 1; i <= n; ++i)for(int j = V; j >= v[i]; --j)if(dp[j - v[i]] != -1) dp[j] = max(dp[j], dp[j - v[i]] + w[i]);cout << (dp[V] == -1 ? 0 : dp[V]) << endl;return 0;
}
這是一維ac代碼
2.分割等和子集
416. 分割等和子集
給你一個?只包含正整數(shù)?的?非空?數(shù)組?nums
?。請你判斷是否可以將這個數(shù)組分割成兩個子集,使得兩個子集的元素和相等
1.狀態(tài)表示:用dp[ i ][ j ]表示選到第 i 個數(shù), 和恰好?j 情況是否存在
2.狀態(tài)轉(zhuǎn)移方程:dp[ i ][ j ]?= dp[ i - 1 ][ j ] || ( j >= nums[ i - 1 ] ?&& dp[ i - 1 ][ j - nums[ i - 1 ] ] )?
3.初始化:根據(jù)題目初始化(見注意)
4.填表順序:從上往下每一行
5.返回值:dp[ n?][ k?]
注意:將題目轉(zhuǎn)換為找出數(shù)組和一半的子序列,k = sum / 2,這樣當(dāng) j?= 0時dp[ i ][ 0 ] = true,且如果sum是奇數(shù)也可以直接返回false
class Solution {
public:bool canPartition(vector<int>& nums) {int n = nums.size();int sum = 0;for(int e : nums) sum += e;if(sum % 2) return false;int k = sum / 2;vector<vector<bool>> dp(n + 1, vector<bool>(k + 1));for(int i = 0; i <= n; ++i) dp[i][0] = true;for(int i = 1; i <= n; ++i)for(int j = 1; j <= k; ++j)dp[i][j] = dp[i - 1][j] || (j >= nums[i - 1] && dp[i - 1][j - nums[i - 1]]);return dp[n][k]; }
};
?這是二維ac代碼
class Solution {
public:bool canPartition(vector<int>& nums) {int n = nums.size();int sum = 0;for(int e : nums) sum += e;if(sum % 2) return false;int k = sum / 2;vector<bool> dp(k + 1);dp[0] = true;for(int i = 1; i <= n; ++i)for(int j = k; j >= nums[i - 1]; --j)dp[j] = dp[j] || dp[j - nums[i - 1]];return dp[k]; }
};
這是一維ac代碼
3.目標(biāo)和
494. 目標(biāo)和
給你一個非負(fù)整數(shù)數(shù)組?nums
?和一個整數(shù)?target
?。
向數(shù)組中的每個整數(shù)前添加?'+'
?或?'-'
?,然后串聯(lián)起所有整數(shù),可以構(gòu)造一個?表達(dá)式?:
- 例如,
nums = [2, 1]
?,可以在?2
?之前添加?'+'
?,在?1
?之前添加?'-'
?,然后串聯(lián)起來得到表達(dá)式?"+2-1"
?。
返回可以通過上述方法構(gòu)造的、運(yùn)算結(jié)果等于?target
?的不同?表達(dá)式?的數(shù)目
轉(zhuǎn)換
設(shè)正數(shù)和為a,負(fù)數(shù)和絕對值為b,則 a + b = sum, a - b = target,于是有a = (sum + target) / 2,所以只要找出和為a的子序列即可,注意當(dāng)(sum + target) 是奇數(shù)以及 a 小于0時直接返回0
1.狀態(tài)表示:用dp[ i ][ j ]表示選到第 i 個數(shù), 和恰好?j 情況數(shù)目
2.狀態(tài)轉(zhuǎn)移方程:dp[ i ][ j ]?= dp[ i - 1 ][ j ] +? dp[ i - 1 ][ j - nums[ i - 1 ] ]
3.初始化:dp[ 0 ][ 0 ] = 1;
4.填表順序:從上往下每一行
5.返回值:dp[ n?][ k?]
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0, n = nums.size();for(int e : nums) sum += e;int k = (target + sum) / 2;if(k < 0 || (sum + target) % 2) return false;vector<vector<int>> dp(n + 1, vector<int>(k + 1));dp[0][0] = 1;for(int i = 1; i <= n; ++i)for(int j = 0; j <= k; ++j){dp[i][j] = dp[i - 1][j];if(j >= nums[i - 1]) dp[i][j] += dp[i - 1][j - nums[i - 1]];}return dp[n][k];}
};
這是二維ac代碼
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0, n = nums.size();for(int e : nums) sum += e;int k = (target + sum) / 2;if(k < 0 || (sum + target) % 2) return false;vector<int> dp(k + 1);dp[0] = 1;for(int i = 1; i <= n; ++i)for(int j = k; j >= nums[i - 1]; --j)dp[j] += dp[j - nums[i - 1]];return dp[k];}
};
這是一維ac代碼
4.最后一塊石頭的重量
1049. 最后一塊石頭的重量 II
有一堆石頭,用整數(shù)數(shù)組?stones
?表示。其中?stones[i]
?表示第?i
?塊石頭的重量。
每一回合,從中選出任意兩塊石頭,然后將它們一起粉碎。假設(shè)石頭的重量分別為?x
?和?y
,且?x <= y
。那么粉碎的可能結(jié)果如下:
- 如果?
x == y
,那么兩塊石頭都會被完全粉碎; - 如果?
x != y
,那么重量為?x
?的石頭將會完全粉碎,而重量為?y
?的石頭新重量為?y-x
。
最后,最多只會剩下一塊?石頭。返回此石頭?最小的可能重量?。如果沒有石頭剩下,就返回?0
。
轉(zhuǎn)換,從數(shù)組中挑選一堆石頭使其接近 sum / 2,再使剩下的石頭重量與其做差即可
于是我們要找到重量小于 sum / 2 的最大重量
1.狀態(tài)表示:用dp[ i ][ j ]表示選到第 i 個數(shù),重量不大于 j 的最大重量
2.狀態(tài)轉(zhuǎn)移方程:dp[ i ][ j ]?=?max(dp[ i - 1 ][ j ], dp[ i - 1 ][ j - nums[ i - 1 ] ] + nums[ i - 1 ] )
3.初始化:無需初始化
4.填表順序:從上往下每一行
5.返回值:dp[ n?][ k?]
class Solution {
public:int lastStoneWeightII(vector<int>& nums) {int sum = 0, n = nums.size();for(int e : nums) sum += e;int k = sum / 2;vector<vector<int>> dp(n + 1, vector<int>(k + 1));for(int i = 1; i <= n; ++i)for(int j = 1; j <= k; ++j){dp[i][j] = dp[i - 1][j];if(j >= nums[i - 1]) dp[i][j] = max(dp[i][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);}return sum - dp[n][k] * 2;}
};
這是二維ac代碼
class Solution {
public:int lastStoneWeightII(vector<int>& nums) {int sum = 0, n = nums.size();for(int e : nums) sum += e;int k = sum / 2;vector<int> dp(k + 1);for(int i = 1; i <= n; ++i)for(int j = k; j >= nums[i - 1]; --j)dp[j] = max(dp[j], dp[j - nums[i - 1]] + nums[i - 1]);return sum - dp[k] * 2;}
};
這是一維ac代碼
B.完全背包
5.完全背包模板題
【模板】完全背包_??皖}霸_牛客網(wǎng) (nowcoder.com)
你有一個背包,最多能容納的體積是V。
現(xiàn)在有n種物品,每種物品有任意多個,第i種物品的體積為𝑣𝑖vi??,價值為𝑤𝑖wi?。
(1)求這個背包至多能裝多大價值的物品?
(2)若背包恰好裝滿,求至多能裝多大價值的物品?
第一問
1.狀態(tài)表示:用dp[ i ][ j ]表示選到第 i 個物品, 體積不超過 j ,物品的最大價值
2.狀態(tài)轉(zhuǎn)移方程:dp[ i ][ j ] = max(dp[ i - 1 ][ j ], dp[ i?][ j - v[ i ] ] + w[ i ] )
3.初始化:無需初始化
4.填表順序:從上往下每一行
5.返回值:dp[ n?][ V?]
第二問
1.狀態(tài)表示:用dp[ i ][ j ]表示選到第 i 個物品, 體積恰好?j ,物品的最大價值
2.狀態(tài)轉(zhuǎn)移方程:dp[ i ][ j ] = max(dp[ i - 1 ][ j ], dp[ i?][ j - v[ i ] ] + w[ i ] )
3.初始化:根據(jù)題目初始化(見注意)
4.填表順序:從上往下每一行
5.返回值:dp[ n?][ V?]
注意:由于dp狀態(tài)表示地特殊性,可能存在無法使?fàn)顟B(tài)存在的情況,所以我們規(guī)定用 - 1 來表示狀態(tài)不存在,于是在 j >= 1使,dp[ 0 ][ j ] = -1,在打印值時,也需要提前特判
#include<iostream>
#include<vector>
#include<string.h>using namespace std;const int N = 1010;
int n, V, v[N], w[N];int dp[N][N];int main()
{cin >> n >> V;for(int i = 1; i <= n; ++i)cin >> v[i] >> w[i];for(int i = 1; i <= n; ++i)for(int j = 1; j <= V; ++j){dp[i][j] = dp[i - 1][j];if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);}cout << dp[n][V] << endl;memset(dp, 0, sizeof dp);for(int j = 1; j <= V; ++j) dp[0][j] = -1;for(int i = 1; i <= n; ++i)for(int j = 1; j <= V; ++j){dp[i][j] = dp[i - 1][j];if(j >= v[i] && dp[i][j - v[i]] != -1) dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);}cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;return 0;
}
這是二維ac代碼
#include<iostream>
#include<vector>
#include<string.h>using namespace std;const int N = 1010;
int n, V, v[N], w[N];int dp[N];int main()
{cin >> n >> V;for(int i = 1; i <= n; ++i)cin >> v[i] >> w[i];for(int i = 1; i <= n; ++i)for(int j = v[i]; j <= V; ++j)dp[j] = max(dp[j], dp[j - v[i]] + w[i]);cout << dp[V] << endl;memset(dp, 0, sizeof dp);for(int j = 1; j <= V; ++j) dp[j] = -1;for(int i = 1; i <= n; ++i)for(int j = v[i]; j <= V; ++j)if(dp[j - v[i]] != -1) dp[j] = max(dp[j], dp[j - v[i]] + w[i]);cout << (dp[V] == -1 ? 0 : dp[V]) << endl;return 0;
}
這是一維ac代碼
6.零錢兌換
322. 零錢兌換
給你一個整數(shù)數(shù)組?coins
?,表示不同面額的硬幣;以及一個整數(shù)?amount
?,表示總金額。
計算并返回可以湊成總金額所需的?最少的硬幣個數(shù)?。如果沒有任何一種硬幣組合能組成總金額,返回?-1
?。
你可以認(rèn)為每種硬幣的數(shù)量是無限的
1.狀態(tài)表示:用dp[ i ][ j ]表示選到第 i 個硬幣, 價值恰好等于?j ,最小的數(shù)目
2.狀態(tài)轉(zhuǎn)移方程:dp[ i ][ j ]?= min(dp[ i - 1 ][ j ], dp[ i ][ j - coins[ i - 1 ] ] + 1)
3.初始化:dp[ 0 ][ j ] = 0x3f3f3f3f
4.填表順序:從上往下每一行
5.返回值:dp[ n?][ am?]
注意:由于可能選擇方案無法構(gòu)成 j ,用0x3f3f3f3f來表示該狀態(tài)不存在,同時在返回值時也需特判
class Solution {
public:int coinChange(vector<int>& coins, int amount) {const int INF = 0x3f3f3f3f;int n = coins.size();vector<vector<int>> dp(n + 1, vector<int>(amount + 1));for(int j = 1; j <= amount; ++j) dp[0][j] = INF;for(int i = 1; i <= n; ++i)for(int j = 1; j <= amount; ++j){dp[i][j] = dp[i - 1][j];if(j >= coins[i - 1]) dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);}return (dp[n][amount] == INF ? -1 : dp[n][amount]);}
這是二維ac代碼
class Solution {
public:int coinChange(vector<int>& coins, int amount) {const int INF = 0x3f3f3f3f;int n = coins.size();vector<int> dp(amount + 1);for(int j = 1; j <= amount; ++j) dp[j] = INF;for(int i = 1; i <= n; ++i)for(int j = coins[i - 1]; j <= amount; ++j)dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);return (dp[amount] == INF ? -1 : dp[amount]);}
};
這是一維ac代碼
7.零錢兌換II
給你一個整數(shù)數(shù)組?coins
?表示不同面額的硬幣,另給一個整數(shù)?amount
?表示總金額。
請你計算并返回可以湊成總金額的硬幣組合數(shù)。如果任何硬幣組合都無法湊出總金額,返回?0
?。
假設(shè)每一種面額的硬幣有無限個。?
題目數(shù)據(jù)保證結(jié)果符合 32 位帶符號整數(shù)。
1.狀態(tài)表示:用dp[ i ][ j ]表示選到第 i 個硬幣, 價值恰好等于?j ,組合的總數(shù)
2.狀態(tài)轉(zhuǎn)移方程:dp[ i ][ j ]?= dp[ i - 1 ][ j ] +?dp[ i ][ j - coins[ i - 1 ] ]
3.初始化:dp[ 0 ][ 0 ] = 1;
4.填表順序:從上往下每一行
5.返回值:dp[ n?][ am?]
class Solution {
public:int change(int amount, vector<int>& coins) {int n = coins.size();vector<vector<int>> dp(n + 1, vector<int>(amount + 1));dp[0][0] = 1;for(int i = 1; i <= n; ++i)for(int j = 0; j <= amount; ++j){dp[i][j] = dp[i - 1][j];if(j >= coins[i - 1]) dp[i][j] += dp[i][j - coins[i - 1]];}return dp[n][amount];}
};
這是二維ac代碼
class Solution {
public:int change(int amount, vector<int>& coins) {int n = coins.size();vector<int> dp(amount + 1);dp[0] = 1;for(int i = 1; i <= n; ++i)for(int j = coins[i - 1]; j <= amount; ++j)dp[j] += dp[j - coins[i - 1]];return dp[amount];}
};
這是一維ac代碼
8.完全平方數(shù)
給你一個整數(shù)?n
?,返回?和為?n
?的完全平方數(shù)的最少數(shù)量?。
完全平方數(shù)?是一個整數(shù),其值等于另一個整數(shù)的平方;換句話說,其值等于一個整數(shù)自乘的積。例如,1
、4
、9
?和?16
?都是完全平方數(shù),而?3
?和?11
?不是。
1.狀態(tài)表示:用dp[ i ][ j ]表示選到第 i 個數(shù), 價值恰好等于?j ,所需平方數(shù)的最小數(shù)目
2.狀態(tài)轉(zhuǎn)移方程:dp[ i ][ j ]?= dp[ i - 1 ][ j ] +?dp[ i ][ j - i * i ] + 1
3.初始化:dp[ 0 ][ 0 ] = 1;其他全部初始化為0x3f3f3f3f
4.填表順序:從上往下每一行
5.返回值:dp[ n?][ k?]
注意:由于題目的特殊性,這里的“體積” k = sqrt( n ),而對于狀態(tài)表示無意義的dp我們用0x3f3f3f3f標(biāo)識,同時,返回數(shù)據(jù)時也要特判
class Solution {
public:int numSquares(int n) {const int INF = 0x3f3f3f3f;int k = sqrt(n);vector<vector<int>> dp(k + 1, vector<int>(n + 1, INF));dp[0][0] = 0;for(int i = 1; i <= k; ++i)for(int j = 0; j <= n; ++j){dp[i][j] = dp[i - 1][j];if(j >= i * i) dp[i][j] = min(dp[i][j], dp[i][j - i * i] + 1);}return dp[k][n] == INF ? 0 : dp[k][n];}
};
這是二維ac代碼
class Solution {
public:int numSquares(int n) {const int INF = 0x3f3f3f3f;int k = sqrt(n);vector<int> dp(n + 1, INF);dp[0] = 0;for(int i = 1; i <= k; ++i)for(int j = i * i; j <= n; ++j)dp[j] = min(dp[j], dp[j - i * i] + 1);return dp[n] == INF ? 0 : dp[n];}
};
這是一維ac代碼
C.二維費(fèi)用的背包問題
9.一和零
474. 一和零
給你一個二進(jìn)制字符串?dāng)?shù)組?strs
?和兩個整數(shù)?m
?和?n
?。
請你找出并返回?strs
?的最大子集的長度,該子集中?最多?有?m
?個?0
?和?n
?個?1
?。
如果?x
?的所有元素也是?y
?的元素,集合?x
?是集合?y
?的?子集
1.狀態(tài)表示:用dp[ i ][ j ][ k ]表示選到第 i 個數(shù),0 數(shù)目小于 j ,1數(shù)目小于 k 的最大字符串?dāng)?shù)
2.狀態(tài)轉(zhuǎn)移方程:dp[ i ][ j ][ k ] = max(dp[ i - 1 ][ j ][ k ], dp[ i - 1 ][ j - a ][ k -?b ] + 1)
3.初始化:無需初始化
4.填表順序:從上往下每一行
5.返回值:dp[ len ][ m?][ n ]
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {int len = strs.size();vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));for(int i = 1; i <= len; ++i){string s = strs[i - 1];int a = 0, b = 0;for(auto e : s)if(e == '0') ++a;else ++b;for(int j = 0; j <= m; ++j)for(int k = 0; k <= n; ++k){dp[i][j][k] = dp[i - 1][j][k];if(j >= a && k >= b)dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - a][k - b] + 1);}}return dp[len][m][n];}
};
這是二維ac代碼
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {int len = strs.size();vector<vector<int>> dp(m + 1, vector<int>(n + 1));for(int i = 1; i <= len; ++i){string s = strs[i - 1];int a = 0, b = 0;for(auto e : s)if(e == '0') ++a;else ++b;for(int j = m; j >= a; --j)for(int k = n; k >= b; --k)dp[j][k] = max(dp[j][k], dp[j - a][k - b] + 1);}return dp[m][n];}
};
這是一維ac代碼
10.盈利計劃
集團(tuán)里有?n
?名員工,他們可以完成各種各樣的工作創(chuàng)造利潤。
第?i
?種工作會產(chǎn)生?profit[i]
?的利潤,它要求?group[i]
?名成員共同參與。如果成員參與了其中一項工作,就不能參與另一項工作。
工作的任何至少產(chǎn)生?minProfit
?利潤的子集稱為?盈利計劃?。并且工作的成員總數(shù)最多為?n
?。
有多少種計劃可以選擇?因為答案很大,所以?返回結(jié)果模?10^9 + 7
?的值
1.狀態(tài)表示:用dp[ i ][ j ][ k ]表示選到第 i 個計劃,員工數(shù)目不大于 j ,利潤不小于 k?
2.狀態(tài)轉(zhuǎn)移方程:dp[ i ][ j ][ k ] = (dp[ i - 1 ][ j ][ k ] + dp[ i - 1 ][ j - g[ i - 1 ] ] [max(0, k - p[ i - 1 ] ) ] ) % a;
3.初始化:dp[ 0 ][ j ][ 0 ]? = 1
4.填表順序:從上往下每一行
5.返回值:dp[ m?][ n?][ mP?]
class Solution {
public:int profitableSchemes(int n, int mP, vector<int>& g, vector<int>& p) {const int a = 1e9 + 7;int m = g.size();vector<vector<vector<int>>> dp(m + 1, vector<vector<int>>(n + 1, vector<int>(mP + 1)));for(int j = 0; j <= n; ++j)dp[0][j][0] =1;for(int i = 1; i <= m; ++i)for(int j = 0; j <= n; ++j)for(int k = 0; k <= mP; ++k){dp[i][j][k] = dp[i - 1][j][k];if(j >= g[i - 1])dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - g[i - 1]][max(0, k - p[i - 1])]) % a;}return dp[m][n][mP];}
};
這是二維ac代碼
class Solution {
public:int profitableSchemes(int n, int mP, vector<int>& g, vector<int>& p) {const int a = 1e9 + 7;int m = g.size();vector<vector<int>> dp(n + 1, vector<int>(mP + 1));for(int j = 0; j <= n; ++j)dp[j][0] =1;for(int i = 1; i <= m; ++i)for(int j = n; j >= g[i - 1]; --j)for(int k = 0; k <= mP; ++k)dp[j][k] = (dp[j][k] + dp[j - g[i - 1]][max(0, k - p[i - 1])]) % a;return dp[n][mP];}
};
這是一維ac代碼
D.似包非包
11.組合總數(shù)IV
給你一個由?不同?整數(shù)組成的數(shù)組?nums
?,和一個目標(biāo)整數(shù)?target
?。請你從?nums
?中找出并返回總和為?target
?的元素組合的個數(shù)。
題目數(shù)據(jù)保證答案符合 32 位整數(shù)范圍
1.狀態(tài)表示:用dp[ i ]表示數(shù) i 被構(gòu)造的排列次數(shù)
2.狀態(tài)轉(zhuǎn)移方程:dp[ i ] += dp[ i - x ];
3.初始化:dp[ 0 ] = 1
4.填表順序:從左往右
5.返回值:dp[ target?]
class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<double> dp(target + 1);dp[0] = 1;for(int i = 1; i <= target; ++i)for(auto x : nums)if(i >= x)dp[i] += dp[i - x];return dp[target];}
};
這是ac代碼
12.不同的二叉搜索樹
96. 不同的二叉搜索樹
給你一個整數(shù)?n
?,求恰由?n
?個節(jié)點組成且節(jié)點值從?1
?到?n
?互不相同的?二叉搜索樹?有多少種?返回滿足題意的二叉搜索樹的種數(shù)。
1.狀態(tài)表示:用dp[ i ]表示 1 到 n 可以組成二叉搜索數(shù)的個數(shù)
2.狀態(tài)轉(zhuǎn)移方程:dp[ i ] += dp[ k - 1 ] * dp[ i - k ] ;
3.初始化:dp[ 0 ] = 1
4.填表順序:從左往右
5.返回值:dp[ n ]
class Solution {
public:int numTrees(int n) {vector<int> dp(n + 1);dp[0] = 1;for(int i = 1; i <= n; ++i)for(int k = 1; k <= i; ++k)dp[i] += dp[k - 1] * dp[i - k];return dp[n];}
};
這是ac代碼