動態(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代碼