目录
一、一和零
二、 盈利计划
三、组合总和IV
四、不同的二叉搜索树
一、一和零
一和零
第一步：确定状态表示
dp[i][j][k]：表示从前 i 个字符串中选，字符 ‘0’ 的个数不超过 j，字符 ‘1’ 的个数不超过 k 时，所有的选法中，长度最大的子集的长度。
第二步：推出状态转移方程
第三步：初始化dp表
其实不需要初始化dp表，只需要在循环遍历的时候保证 i 是从小到大的即可。
解题代码：
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++){int zeronum = 0, onenum = 0;for(auto s : strs[i-1]){if(s == '0')zeronum++;elseonenum++;}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 >= zeronum && k >= onenum)dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-zeronum][k-onenum] + 1);}}}return dp[len][m][n];}
}; 
二、 盈利计划
盈利计划
第一步：确定状态表示
dp[i][j][k]：从前 i 个工作中选，完成这些工作的人数不超过 j，所获的利润至少为 k 时，一共有多少种选法。
第二步：推出状态转移方程
第三步：初始化dp表
我们这里只需要初始化没有任务的情况，即：i == 0。既然没有任务，那么利润就一定为0。
所以我们需要初始化 dp[0][j][0] == 1。
解题代码：
class Solution
{
public:const int MOD = 1e9 + 7;int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {int len = group.size();vector<vector<vector<int>>> dp(len+1, vector<vector<int>>(n+1, vector<int>(minProfit+1)));for(int i = 0; i <= n; i++)dp[0][i][0] = 1;for(int i = 1; i <= len; i++){for(int j = 0; j <= n; j++){for(int k = 0; k <= minProfit; k++){dp[i][j][k] += dp[i-1][j][k];if(j >= group[i-1])dp[i][j][k] += dp[i-1][j-group[i-1]][max(0, k-profit[i-1])];dp[i][j][k] %= MOD;}}}return dp[len][n][minProfit];}
}; 
三、组合总和IV
组合总和IV
第一步：确定状态表示
dp[i]：表示凑成总和为 i，一共有多少种排列数。
第二步：推出状态转移方程
第三步：初始化dp表
dp[0] = 1。
解题代码：
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];}
};
四、不同的二叉搜索树
不同的二叉搜索树
第一步：确定状态表示
dp[i]：表示结点个数为 i 的个时候，一共有多少种二叉搜索树。
第三步：推出状态转移方程
dp[i] += dp[j - 1] * dp[i - j]
第三步：初始化dp表
dp[0] = 1。
解题代码：
class Solution
{
public:int numTrees(int n) {vector<int> dp(n+1);dp[0] = 1;for(int i = 1; i <= n; i++){for(int j = 1; j <= i; j++) // 枚举根节点{dp[i] += dp[j-1] * dp[i-j];}}return dp[n];}
}; 