当前位置：首页 > news >正文

动态规划58道算法题

news 2024/10/22 9:31:25

一斐波那契数列模型

1.第N个泰波那契数

2三步问题

3使用最小花费爬楼梯

4解码方法

二路径问题

1不同的路径

2不同的路径Ⅱ

3珠宝的最高价值

4下降路径最小和

5最小路径和

6地下城游戏

三多状态

1按摩师

2打家劫舍Ⅱ

3删除并获得点数

4粉刷房子

5买卖股票的最佳时期含冷冻期

6买卖股票的最佳时期含手续费

7买卖股票的最佳时期Ⅲ

8买卖股票的最佳时期Ⅳ

四子数组系列

1最大子数组和

2环形子数组的最大和

3乘积最大子数组

4乘积为正数的最大子数组

5等差数列划分

6最长湍流子数组

7单词拆分

8环绕字符串中唯一的子字符串

五子序列系列

1最长递增子序列

2摆动序列

3最长递增子序列的个数

4最长数对链

5最长定差子序列

6最长的斐波那契子序列的长度

7最长等差数列

8等差数列划分

六回文串问题

1回文子串

2最长回文子串

3分割回文串IV

4分割回文串 II

5最长回文子序列

6让字符串成为回文串的最少插入次数

七两个数组的dp问题

1最长公共子序列

2通配符匹配

3正则表达式匹配

4交错字符串

5两个字符串的最小ASCLL删除和

6最长重复子数组

八01背包问题

0[模板]01背包

编辑

优化

1分割等和子集

2目标和

3最后一块石头的重量 II

九完全背包问题

0[模板]完全背包

1零钱兑换

2零钱兑换Ⅱ

3完全平方数

十二维费用的背包问题

1一和零

2盈利计划

十三似包非包

1组合总和Ⅳ

十四卡特兰数

1不同的二叉搜索树

一斐波那契数列模型

1.第N个泰波那契数

oj链接：第N个泰波那契数

解法：动态规划（分5步）

1状态表示：dp[i]表示到达i位置时的泰波那契数

2确定状态转移方程(按照题目要求+经验)：dp[i] =dp[i-1] + dp[i-2] +dp[i-3]

3初始化：需要用到前三个状态的值，所以：dp[0] = 0 ,dp[1]=1,dp[2]=1;

4填表顺序：从左向右

5返回值：根据状态表示得出：dp[n]

但要注意边界情况提前判断防越界！

class Solution {
public:int tribonacci(int n) {//边界情况if(n==0||n==1) return n;if(n==2) return 1;vector<int> dp(n+1);//初始化dp[0]=0,dp[1]=1,dp[2]=1;//填表for(int i=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2]+dp[i-3];}return dp[n];}
};

利用滚动数组(变量)进行空间优化：

class Solution {
public:int tribonacci(int n) {//边界情况if(n==0||n==1) return n;if(n==2) return 1;//利用滚动数组进行空间优化int a=0,b=1,c=1,d=0;for(int i=2;i<n;i++){d=a+b+c;a=b,b=c,c=d;}return d;}
};

2三步问题

oj链接：三步问题

思路：与上题思路一致，但要注意结果的越界问题

class Solution {
public:int waysToStep(int n) {const int MOD=1e9+7;if(n==1||n==2) return n;if(n==3) return 4;vector<int> dp(n+1);dp[1]=1,dp[2]=2,dp[3]=4;for(int i=4;i<=n;i++){dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%MOD;//防止越界}return dp[n];}
};

3使用最小花费爬楼梯

oj链接：使用最小花费爬楼梯

解法：动态规划（分5步）

思路1：

1状态表示：dp[i]表示从开始位置，到达i位置时（不是楼顶）的最小花费

2确定状态转移方程(按照题目要求+经验)：

有两种到达方式：1.从i-1位置到达i位置；2.从i-2位置到达i位置;

取两者的最小值即可；所以：dp[i] =min(dp[i-1],dp[i-2])+cost[i-1]

3初始化：需要用到前两个状态的值，所以：dp[0] = 0(还没开始爬楼梯) ,dp[1]=cost[0]

4填表顺序：从左向右

5返回值：从n-1到达楼顶还是n位置到达楼顶的最小花费不确定；所以：min(dp[n],dp[n-1])

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();vector<int> dp(n+1);dp[0]=0,dp[1]=cost[0];for(int i=2;i<=n;i++){dp[i]=min(dp[i-1],dp[i-2])+cost[i-1];}return min(dp[n],dp[n-1]);}
};

思路2：

1状态表示：dp[i]表示到达i位置的最小花费

2确定状态转移方程(按照题目要求+经验)：

有两种到达方式：1.到达i-1位置时花费cost[i-1]；

2.到达i-2位置时花费cost[i-2];取两者的最小值即可

所以：dp[i] =min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

3初始化：需要用到前两个状态的值，所以：dp[0]=dp[1]=0(到达0或者1下标没有花费)

4填表顺序：从左向右

5返回值：dp[n]

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();vector<int> dp(n+1);for(int i=2;i<=n;i++){dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[n];}
};

思路3:

1状态表示：dp[i]表示从i位置处出发，到达楼顶时的最小花费

2确定状态转移方程(按照题目要求+经验)：

有两种到达方式：1.花费cost[i]到达i+1位置，从i+1位置到达楼顶的最小花费

2.花费cost[i]到达i+2位置，从i+2位置到达楼顶的最小花费

所以：dp[i] =min(dp[i+1]+cost[i],dp[i+2]+cost[i])

3初始化：需要用到后两个状态的值，所以：dp[n-1]=cost[n-1],dp[n-2]=cost[n-2]

4填表顺序：为了不越界，从右向左进行填表

5返回值：从0位置开始还是1位置开始不确定，所以：min(dp[0],dp[1])

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();vector<int> dp(n);dp[n-1]=cost[n-1],dp[n-2]=cost[n-2];for(int i=n-3;i>=0;i--){dp[i]=min(dp[i+1]+cost[i],dp[i+2]+cost[i]);}return min(dp[0],dp[1]);}
};

4解码方法

oj链接：解码方法

解法：动态规划（分5步）

思路：

1状态表示：dp[i]表示i位置时的解码方法的总数

2确定状态转移方程(按照题目要求+经验)：

共有2种情况：

1单独解码：

a.s[i]字符解码成功时，总的解码总数在dp[i-1]里，所以：dp[i]=dp[i-1]（千万不能+1！）

b.s[i]字符解码失败时，dp[i]=0

2与s[i-1]组合进行解码：

a.s[i-1]与s[i]字符组合解码成功时，dp[i]=dp[i-2]（与上面类似）

b.s[i-1]与s[i]字符组合解码失败时，dp[i]=0

所以状态转移方程：dp[i]是这两种情况之和！！

3初始化：多开一个辅助节点来方便我们初始化:

dp[0]=1,dp[1]=s[0]!=‘0’（只要不是‘0’就是解码成功）

4填表顺序：从左向右进行填表

5返回值：dp[n]

class Solution {
public:int numDecodings(string s) {int n=s.size();vector<int> dp(n+1);dp[0]=1;if(s[0]!='0') dp[1]=1;//多开一个节点要注意下标的映射关系for(int i=2;i<=n;i++){if(s[i-1]!='0') dp[i]+=dp[i-1];//如果解码失败就不进来 就是=0情况!!int tmp=(s[i-2]-'0')*10+(s[i-1]-'0');//为什么不是[0,26]？->01,01,03...09都是解码失败！！if(tmp>=10&&tmp<=26) dp[i]+=dp[i-2];}return dp[n];}
};

二路径问题

1不同的路径

oj链接：不同路径

解法：动态规划（分5步）

思路：

1状态表示：dp[i][j]表示到达[i,j]位置时不同路径的总数

2确定状态转移方程(按照题目要求+经验)：

由于有可能是从上面（dp[i-1][j]）到达[i,j]位置

也有可能是从左边（dp[i][j-1]）到达[i,j]位置

所以：dp[i][j] = dp[i-1][j] + dp[i][j-1]

3初始化：要用到上面与左边的位置(还要保证不越界)：多开一个一行，多开一列来解决；

dp[0][1]=1,其它为0即可

（为了保证与起点同一行/同一列的值都是1,不干扰状态转移方程计算的结果）

4填表顺序： (保证上面与左边的值是更新过的)从上往下，从左向右进行依次填表

5返回值：dp[m][n]

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m+1,vector<int>(n+1));dp[0][1]=1;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m][n];}
};

2不同的路径Ⅱ

oj链接：不同路径 II

思路：与上题类似，只不过要注意下标的映射关系即可~

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int n=obstacleGrid.size(),m=obstacleGrid[0].size();vector<vector<int>> dp(n+1,vector<int>(m+1));dp[0][1]=1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(obstacleGrid[i-1][j-1]==0) dp[i][j]=dp[i-1][j]+dp[i][j-1];//注意下标的映射}}return dp[n][m];}
};

3珠宝的最高价值

oj链接：珠宝的最高价值

解法：动态规划（分5步）

思路：

1状态表示：dp[i][j]表示到达[i,j]位置时珠宝的最高价值

2确定状态转移方程(按照题目要求+经验)：

由于有可能是从上面（dp[i-1][j]）到达[i,j]位置

也有可能是从左边（dp[i][j-1]）到达[i,j]位置

要想得到当前位置的珠宝的最高价值：取这两者的最大值 + 当前珠宝的价值即可

3初始化：要用到上面与左边的位置(还要保证不越界)：多开一个一行，多开一列来解决；

题目范围都是正数；vector初始化默认为0；

取最大值不受影响，所以不用初始化

4填表顺序： (保证上面与左边的值是更新过的)从上往下，从左向右进行依次填表

5返回值：dp[m][n]

class Solution {
public:int jewelleryValue(vector<vector<int>>& frame) {int n=frame.size(),m=frame[0].size();vector<vector<int>> dp(n+1,vector<int>(m+1));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];}}return dp[n][m];}
};

4下降路径最小和

oj链接：下降路径最小和

解法：动态规划（分5步）

思路：

1状态表示：dp[i][j]表示到达[i,j]位置时下降路径最小和

2确定状态转移方程(按照题目要求+经验)：

由于有可能是从上面（dp[i-1][j]）到达[i,j]位置

也有可能是从左边（dp[i-1][j-1]）到达[i,j]位置

也可能是从右边（dp[i-1][j+1]）d到达[i,j]位置

所以：取这三者的最小值 + 当前位置的值即可

3初始化：要用到上面与左边的位置(还要保证不越界)：多开两列来解决；

取最小值时不受影响，要初始化为INT_MAX

4填表顺序： (保证上面与左边的值是更新过的)从上往下（从左往右）进行依次填表

5返回值：最后一行找出最小的dp值即为答案

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {int n=matrix.size(),m=matrix[0].size();vector<vector<int>> dp(n+1,vector<int>(m+2,0x3f3f3f3f));//多开两列for(int j=1;j<=m;j++) dp[0][j]=matrix[0][j-1];//(到达第一行的路径和是它本身)for(int i=1;i<n;i++){for(int j=1;j<=m;j++){dp[i][j]=min(dp[i-1][j],min(dp[i-1][j-1],dp[i-1][j+1]))+matrix[i][j-1];}}int ret=0x3f3f3f3f;for(int j=1;j<=m;j++) ret=min(ret,dp[n-1][j]);return ret;}
};

也可以是多开一行，两列进行初始化：

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {int m=matrix.size();//开大空间vector<vector<int>> dp(m+1,vector<int>(m+2,INT_MAX));for(int i=0;i<m+2;i++) dp[0][i]=0;//填表时不受影响for(int i=1;i<=m;i++){for(int j=1;j<=m;j++){dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1]))+matrix[i-1][j-1];} }int ret=INT_MAX;for(int j=1;j<=m;j++) ret=min(dp[m][j],ret);return ret;}
};

5最小路径和

oj链接：最小路径和

解法：动态规划（分5步）

思路：

1状态表示：dp[i][j]表示到达[i,j]位置时最小路径最小和

2确定状态转移方程(按照题目要求+经验)：

由于有可能是从上面（dp[i-1][j]）到达[i,j]位置

也有可能是从左边（dp[i-1][j-1]）到达[i,j]位置

所以：取这两者者的最小值 + 当前位置的值即可

3初始化：要用到上面与左边的位置(还要保证不越界)：多开一行一列来解决；

取最最大值时不受影响，要初始化为INT_MIN；

(dp[0][1] = 0保证填表不影响最终结果(与不同的路径思路一样))

4填表顺序： (保证上面与左边的值是更新过的)从上往下（从左往右）进行依次填表

5返回值：dp[n][m]

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int n=grid.size(),m=grid[0].size();vector<vector<int>> dp(n+1,vector<int>(m+1,0x3f3f3f3f));dp[0][1]=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];}}return dp[n][m];}
};

6地下城游戏

oj链接：地下城游戏

解法：动态规划（分5步）

思路：

状态表示：dp[i][j]表示到达[i,j]位置时此时的最小血量：如果这样定义的话就坑啦！

因为方格中有正数，有负数，你在到达[i,j]位置时可能是需要多次调整初始血量才能到达！

1状态表示(正确)：dp[i][j]表示从从[i,j]位置出发到达右下角所需的最小血量

2确定状态转移方程(按照题目要求+经验)：

从[i,j]位置到达右下角有两步：

a.到达[i][j+1]位置,从该位置到达右下角

b.到达[i+1][j]位置,从该位置到达右下角;

a.设[i,j]位置的值为x,你要保证到达[i][j+1]位置后剩余血量是不死(>0)，所以：

x + dp[i][j] >= dp[i][j+1] -->

dp[i][j] >= dp[i][j+1] - x

但有可能x值过大导致dp[i][j]是负数，这种状态：死后吃了血包复活了是不被允许的！！

所以要进行特判：dp[i][j] = max(dp[i][j]，1)保证每个时刻状态是活着过来的！！

b也是同样的情况...

所以状态转移方程:

dp[i][j] = max(min(dp[i+1][j]，dp[i][j+1]）- x，1)

3初始化：要用到下面与右边的位置(还要保证不越界)：多开一行一列来解决；

取最最小值时不受影响，要初始化为INT_MAX；

(dp[n][m-1] = 1保证填表不影响最终结果(与不同的路径思路一样))

4填表顺序：从下往上（从右往左）进行依次填表

5返回值：dp[0][0]

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int n=dungeon.size(),m=dungeon[0].size();vector<vector<int>> dp(n+1,vector<int>(m+1,INT_MAX));dp[n][m-1]=1;for(int i=n-1;i>=0;i--){for(int j=m-1;j>=0;j--){dp[i][j]=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];dp[i][j]=max(dp[i][j],1);//dp状态最小是1}}return dp[0][0];}
};

三多状态

1按摩师

oj链接：按摩师

解法：动态规划（分5步）

由于可以进行选与不选两种状态，我们就来定义两种不同的状态

1状态表示：slect[i]表示i位置接受预约,unslect[i]表示当前i位置不接受预约

2确定状态转移方程(按照题目要求+经验)：

由于题目说了：不能接受相邻的预约：

所以当前i位置要进行预约的前提必须是i-1位置得是不接受预约的状态；

而当前i位置不接受预约则不受到i-1位置的约束：可以是接受预约也可以是不接受预约(MAX)

slect[i] = unslect[i-1] + nums[i]

unslect[i] = max(slect[i-1],unslect[i-1])

注：两者的顺序不能颠倒！！

3初始化：slect[0] = nums[0] 即可(unslect[0] = 0创建数组时就已经进行初始化了)

4填表顺序：从左向右

5返回值：题目求的是总的预约时长最长，所以：max(slect[n-1],unslect[n-1])

class Solution {
public:int massage(vector<int>& nums) {int n=nums.size();if(n==0) return 0;vector<int> slect(n);vector<int> unslect(n);slect[0]=nums[0];//第一个位置slect状态必选for(int i=1;i<n;i++){slect[i]=unslect[i-1]+nums[i];//前面没选，此时才能选unslect[i]=max(unslect[i-1],slect[i-1]);//有两种状态可以选}return max(slect[n-1],unslect[n-1]);//最后一个位置选最大的结果}
};

2打家劫舍Ⅱ

oj链接：打家劫舍 II

解法：动态规划（分5步）

由于可以偷与不偷两种状态，我们就来定义两种不同的状态

1状态表示：steal[i]表示i位置可以偷,unsteal[i]表示当前i位置不偷

2确定状态转移方程(按照题目要求+经验)：

steal[i] = unsteal[i-1] + nums[i]

unsteal[i] = max(steal[i-1] , unsteal[i-1])

由于nums[0]与nums[n-1]是连接的关系，我们要分情况讨论：（n=nums.size()）

a）nums[0]位置偷，求的是[2,n-2]位置的最大金额(1和n-1位置不能偷)

b）nums[0]位置不偷，求的是从[1,n-1]位置的偷取的最大金额

求出两者的最大值便是此题的答案~

3初始化：slect[开始位置] = nums[开始位置]

4填表顺序：从左向右

5返回值：返回两种情况的最大值即可

class Solution {
public:int rob(vector<int>& nums) {int n=nums.size();return max(nums[0]+rab1(2,n-2,nums),rab1(1,n-1,nums));}int rab1(int pos,int n,vector<int>& nums){//边界if(pos>n) return 0;vector<int> steal(nums.size());vector<int> unsteal(nums.size());//初始化steal[pos]=nums[pos];for(int i=pos+1;i<=n;i++){steal[i]=unsteal[i-1]+nums[i];unsteal[i]=max(unsteal[i-1],steal[i-1]);}return max(steal[n],unsteal[n]);}
};

也可以理解：第一家不偷，可以偷的范围[1,n-1]；

第一家要偷，可以偷的范[0,n-2] ；(最后一家不偷了啦)

class Solution {
public:int rob(vector<int>& nums) {if(nums.size()==1) return nums[0];//特判return max(rob1(nums,0,nums.size()-2),rob1(nums,1,nums.size()-1));}int rob1(vector<int>& nums,int begin,int end){if(begin>=end) return nums[begin];//指向同一家或者end在begin左边,自己偷begin位置的(end有可能越界)int n=nums.size();vector<int> steal(n);vector<int> unsteal(n);steal[begin]=nums[begin];for(int i=begin+1;i<=end;i++){steal[i]=unsteal[i-1]+nums[i];unsteal[i]=max(unsteal[i-1],steal[i-1]);}return max(steal[end],unsteal[end]);}
};

3删除并获得点数

oj链接：删除并获得点数

思路：

本题要先进行预处理：将nums中的每个值通过下标映射到新数组sum里并相加；

如 nums={1,1,3,5,3,4};进行处理后就变成：sums={0,2,0,6,4,5};

后面的工作就是打家劫舍的问题啦~

class Solution {
public:int deleteAndEarn(vector<int>& nums) {//预处理int sum[10001]={0};for(auto& e:nums){sum[e]+=e;}//打家劫舍vector<int> Delete(10001);vector<int> NoDelete(10001);Delete[0]=sum[0];for(int i=1;i<10001;i++){Delete[i]=NoDelete[i-1]+sum[i];NoDelete[i]=max(Delete[i-1],NoDelete[i-1]);}return max(Delete[10000],NoDelete[10000]);}
};

4粉刷房子

oj链接：粉刷房子

思路：与打家劫舍问题一样，做不过多了个状态而已~

class Solution {
public:int minCost(vector<vector<int>>& costs) {int n=costs.size();vector<int> Red(n),Blue(n),Green(n);Red[0]=costs[0][0],Blue[0]=costs[0][1],Green[0]=costs[0][2];for(int i=1;i<n;i++){Red[i]=min(Blue[i-1],Green[i-1])+costs[i][0];Blue[i]=min(Red[i-1],Green[i-1])+costs[i][1];Green[i]=min(Red[i-1],Blue[i-1])+costs[i][2];}return min(Red[n-1],min(Blue[n-1],Green[n-1]));}
};

5买卖股票的最佳时期含冷冻期

oj链接：买卖股票的最佳时机含冷冻期

对于股票问题中的多个状态，我们可以画出一个状态机模型来表示各个状态之间的关系

解法：动态规划（分5步）

1状态表示：由于有三个状态，我们定义出三个状态表示

b[i]表示从第0到i天时处于‘买入’状态，此时的最大利润

d[i]表示从第0到i天时处于‘可交易’状态，此时的最大利润

f[i]表示从第0到i天是处于‘冷冻期’状态，此时的最大利润

2确定状态转移方程(按照题目要求+经验)：

根据上面的状态机模型，我们可以很清晰来推导出状态转移方程~

b[i] = max(b[i-1] , s[i-1] - price[i])

d[i] = max(d[i-1],f[i-1]);

f[i] = b[i-1] + price[i]

3初始化：b[0] = -price[0]注意这里是买股票的状态，不是price[0]！！

4填表顺序：从左向右

5返回值：max(d[n-1],f[n-1])最后一个状态不可能是买入状态，必亏~

可以是定义多个状态的

class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<int> buy(n),deal(n),freeze(n);buy[0]=-prices[0];for(int i=1;i<n;i++){buy[i]=max(buy[i-1],deal[i-1]-prices[i]);deal[i]=max(freeze[i-1],deal[i-1]);freeze[i]=buy[i-1]+prices[i];}return max(deal[n-1],freeze[n-1]);}
};

也可以写成二维数组的形式

class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>> dp(n,vector<int>(3));//dp[i][0]->买入 dp[i][1]->可交易 dp[i][2]->冷冻期dp[0][0]=-prices[0];//注意初始化!for(int i=1;i<n;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]=max(dp[i-1][1],dp[i-1][2]);dp[i][2]=dp[i-1][0]+prices[i];cout<<dp[i][0]<<' '<<dp[i][1]<<' '<<dp[i][2]<<endl;}return max(dp[n-1][1],dp[n-1][2]);//最后不能是买入状态(只买不出必亏!)}
};

6买卖股票的最佳时期含手续费

oj链接：买卖股票的最佳时机含手续费

思路比上题的股票问题少了一个状态，做起来相对而言会简单一点;

主要问题是手续费到底是在买购票时进行减还是在卖股票时减：其实两种可以的~

(不影响最后求的是最大利润)

卖股票减手续费

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n=prices.size();vector<int> Buy(n),Sole(n);Buy[0]=-prices[0];for(int i=1;i<n;i++){Buy[i]=max(Buy[i-1],Sole[i-1]-prices[i]);Sole[i]=max(Buy[i-1]+prices[i]-fee,Sole[i-1]);}return Sole[n-1];}
};

买股票减手续费

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n=prices.size();vector<int> Buy(n),Sole(n);Buy[0]=-prices[0]-fee;for(int i=1;i<n;i++){Buy[i]=max(Buy[i-1],Sole[i-1]-prices[i]-fee);Sole[i]=max(Buy[i-1]+prices[i],Sole[i-1]);}return Sole[n-1];}
};

7买卖股票的最佳时期Ⅲ

oj链接：买卖股票的最佳时机 III

这次对于买卖股票次数有了限制：但还是先来画出状态机模型

解法：动态规划（分5步）

如果把状态表示定义成一维的话：dp[i]表示第0到i天的最大利润，具体是交易了几次不知道

所以我们要把状态表示修改成二维的~

1状态表示：

Buy[i][j]表示从第0到i天，总成交次数为j次，当前的状态为‘买入’状态，此时的最大利润

Solt[i][j]表示从第0到i天，总成交次数为j次，当前的状态为‘卖出’状态，此时的最大利润

2确定状态转移方程(按照题目要求+经验)：

根据上面的状态机模型，我们可以很清晰来推导出状态转移方程~

Buy[i][j] =max(Buy[i-1][j]，Solt[i-1][j]-price[i])

注意：交易次数的累加是在卖出股票后才+1！！也就是说:从买入到卖出，是会让j+1的

Solt[i][j] = max(Solt[i-1][j]，Buy[i-1][j-1]+price[i])

3初始化：为了填表不受影响，全部初始化为-0x3f3f3f3f（如果是INT_MIN进行-时会越界~）

Buy[0][0] = -price[0]，Solt[0][0] = 0

4填表顺序：从上往下,从左向右

5返回值：求出最后一行（Solt[n-1][j]）的最大值

class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>> Buy(n,vector<int>(3,-0x3f3f3f3f));vector<vector<int>> Solt(n,vector<int>(3,-0x3f3f3f3f));Buy[0][0]=-prices[0],Solt[0][0]=0;for(int i=1;i<n;i++){for(int j=0;j<3;j++){Buy[i][j]=max(Buy[i-1][j],Solt[i-1][j]-prices[i]);Solt[i][j]=Solt[i-1][j];if(j-1>=0) Solt[i][j]=max(Solt[i][j],Buy[i-1][j-1]+prices[i]);// 把股票卖出去时 -> 交易次数++ }}int ans=0;for(int j=0;j<3;j++) ans=max(ans,Solt[n-1][j]);return ans;}
};

8买卖股票的最佳时期Ⅳ

oj链接：买卖股票的最佳时机 IV

与上面的分析思路一毛一样，自己尝试分析试试吧~

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n=prices.size();vector<vector<int>> Buy(n,vector<int>(k+1,-0x3f3f3f3f));vector<vector<int>> Solt(n,vector<int>(k+1,-0x3f3f3f3f));Buy[0][0]=-prices[0],Solt[0][0]=0;for(int i=1;i<n;i++){for(int j=0;j<=k;j++){Buy[i][j]=max(Buy[i-1][j],Solt[i-1][j]-prices[i]);Solt[i][j]=Solt[i-1][j];if(j-1>=0) Solt[i][j]=max(Solt[i][j],Buy[i-1][j-1]+prices[i]);// 把股票卖出去时 -> 交易次数++ }}int ans=0;for(int j=0;j<=k;j++) ans=max(ans,Solt[n-1][j]);//最后一天所有卖出去状态的最大值return ans;}
};

四子数组系列

1最大子数组和

oj链接：最大子数组和

解法：动态规划（分5步）

1状态表示：

dp[i]表示一i位置为结尾的所有子数组的最大和

2确定状态转移方程(按照题目要求+经验)：

有两种情况：

a.(子数组)长度为1：nums[i]

b.(子数组)长度大于1：dp[i-1]+nums[i]

所以：dp[i] = max(dp[i-1]+nums[i],nums[i])

3初始化：

有两种初始化：

a.不添加虚拟节点：vector<int> dp(n) dp[0] = nums[i]

这种初始化要注意：如果数组长度为2时要特殊处理

b.添加虚拟节点：vector<int> dp(n+1) dp[0] = 0(不影响后续填表)

这种初始化要注意：下标的映射关系与虚拟节点的值

4填表顺序：从左往右

5返回值：所有情况下的最大值（注意dp[n]（dp[n-1]）不一定是最大的~）

//没有虚拟节点
class Solution {
public:int maxSubArray(vector<int>& nums) {int tmp=-0x3f3f3f3f,n=nums.size();vector<int> dp(n);dp[0]=nums[0];tmp=max(tmp,dp[0]);for(int i=1;i<n;i++){dp[i]=max(dp[i-1]+nums[i],nums[i]);tmp=max(tmp,dp[i]);}return tmp;}
};//有虚拟节点
class Solution {
public:int maxSubArray(vector<int>& nums) {int tmp=-0x3f3f3f3f,n=nums.size();vector<int> dp(n+1);for(int i=1;i<=n;i++){dp[i]=max(dp[i-1]+nums[i-1],nums[i-1]);tmp=max(tmp,dp[i]);}return tmp;}
};

2环形子数组的最大和

oj链接：环形子数组的最大和

在求解之前，先要进行转化：

解法：动态规划（分5步）

1状态表示：

maxdp[i]表示一i位置为结尾的所有子数组的最大和

mindp[i]表示一i位置为结尾的所有子数组的最小和

2确定状态转移方程(按照题目要求+经验)：

有两种情况：

a.(子数组)长度为1：nums[i]

b.(子数组)长度大于1：maxdp[i-1]+nums[i]

所以：maxdp[i] = max(maxdp[i-1]+nums[i],nums[i])

同理：mindp[i] = min(mindp[i-1]+nums[i],nums[i])

3初始化：

有两种初始化：

a.不添加虚拟节点：vector<int> dp(n) mindp[0] = maxdp[0] = nums[i]

这种初始化要注意：如果数组长度为2时要特殊处理

b.添加虚拟节点：vector<int> dp(n+1) mindp[0] = maxdp[0] = 0(不影响后续填表)

这种初始化要注意：下标的映射关系与虚拟节点的值

4填表顺序：从左往右

5返回值：两种情况的最大值

注：如果子数组全是负数，minret == sum时仅需返回 maxret即可

class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int n=nums.size(),maxret=-0x3f3f3f3f,minret=0x3f3f3f3f,sum=0;vector<int> maxdp(n+1),mindp(n+1);for(int i=1;i<=n;i++){//求最小sum+=nums[i-1];mindp[i]=min(mindp[i-1]+nums[i-1],nums[i-1]);minret=min(minret,mindp[i]);//求最大maxdp[i]=max(maxdp[i-1]+nums[i-1],nums[i-1]);maxret=max(maxret,maxdp[i]);}return sum==minret?maxret:max(maxret,sum-minret);}
};

3乘积最大子数组

oj链接：乘积最大子数组

解法：动态规划（分5步）

1状态表示：

maxdp[i]表示一i位置为结尾的所有子数组的最大乘积

mindp[i]表示一i位置为结尾的所有子数组的最小乘积

2确定状态转移方程(按照题目要求+经验)：

共有两种情况：

当nums[i] <0 时：

maxdp[i] = mindp[i-1]*nums[i]

mindp[i] = min(mindp[i-1]*nums[i],nums[i])

当nums[i] >0 时：

maxdp[i] = max(maxdp[i-1]*nums[i],nums[i])

mindp[i] = maxdp[i-1]*nums[i]

3初始化：

添加虚拟节点：vector<int> dp(n+1) mindp[0] = 1(不影响后续填表)

4填表顺序：从左往右

5返回值：填maxdp[i]过程中的最大值

class Solution {
public:int maxProduct(vector<int>& nums) {int n=nums.size(),ret=-0x3f3f3f3f;vector<int> maxdp(n+1),mindp(n+1);mindp[0]=1;for(int i=1;i<=n;i++){if(nums[i-1]<0){maxdp[i]=mindp[i-1]*nums[i-1];mindp[i]=min(maxdp[i-1]*nums[i-1],nums[i-1]);}else{maxdp[i]=max(maxdp[i-1]*nums[i-1],nums[i-1]);mindp[i]=mindp[i-1]*nums[i-1];}ret=max(ret,maxdp[i]);}return ret;}
};

4乘积为正数的最大子数组

oj链接：乘积为正数的最长子数组长度

解法：动态规划（分5步）

1状态表示：

f[i]表示一i位置为结尾乘积为正数的最大子数组和

g[i]表示一i位置为结尾乘积为负数的最大子数组和(通过分析f[i]分析一个状态解决不了问题)

2确定状态转移方程(按照题目要求+经验)

分情况分析（画图）

3初始化：

有上题类似

4填表顺序：从左往右

5返回值：填f[i]过程的最大值

class Solution {
public:int getMaxLen(vector<int>& nums) {int n=nums.size(),ret=-0x3f3f3f3f;vector<int> maxdp(n+1),mindp(n+1);for(int i=1;i<=n;i++){if(nums[i-1]<0){maxdp[i]=mindp[i-1]==0?0:mindp[i-1]+1;mindp[i]=maxdp[i-1]+1;}else if(nums[i-1]>0){maxdp[i]=maxdp[i-1]+1;mindp[i]=mindp[i-1]==0?0:mindp[i-1]+1;}ret=max(ret,maxdp[i]);}return ret;}
};

5等差数列划分

oj链接：等差数列划分

解法：动态规划（分5步）

1状态表示：

dp[i]表示：以i位置为结尾的所有子数组中是等差数列的子数组的个数

2确定状态转移方程(按照题目要求+经验)

分情况（画图）

3初始化：

dp[1]=dp[0]=0（一个或两个一定不是等差数列）

4填表顺序：从左往右

5返回值：填dp[i]过程所有数相加（题目求等差数列的个数）

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {int n=nums.size(),ret=0;if(n==2||n==1) return ret;vector<int> dp(n);dp[1]=dp[0]=0;for(int i=2;i<n;i++){dp[i]=nums[i]-nums[i-1]==nums[i-1]-nums[i-2]?dp[i-1]+1:0;ret+=dp[i];}return ret;}
};

6最长湍流子数组

oj链接：最长湍流子数组

思路1:

解法：动态规划（分5步）

1状态表示：

dp[i]表示：以i位置为结尾的所有子数组中，最长湍流子数组的长度

2确定状态转移方程(按照题目要求+经验)

a.如果arr[i] arr[i-1] arr[i-2] 满足湍流子数组的定义时：dp[i] = dp[i-1] + 1

b.不满足时:

b1.如果arr[i] != arr[i-1] dp[i] = 2（arr[i]与arr[i-1]一定是湍流子数组）

b2.相等就单独构成 dp[i] = 1

3初始化：

dp表中所有值都初始为1

4填表顺序：从左往右

5返回值：填dp[i]过程找最长长度

class Solution {
public:int maxTurbulenceSize(vector<int>& arr) {int n=arr.size(),ret=-0x3f3f3f3f;if(n==1) return 1;vector<int> dp(n,1);if(arr[1]!=arr[0]) dp[1]+=1;if(n==2) return dp[1];for(int i=2;i<n;i++){if((arr[i]>arr[i-1]&&arr[i-1]<arr[i-2])||(arr[i]<arr[i-1]&&arr[i-1]>arr[i-2])) dp[i]=dp[i-1]+1;else if(arr[i]!=arr[i-1]) dp[i]=2;//从头开始求长度//相等dp[i]=1不用处理了ret=max(ret,dp[i]);}return ret;}
};

思路2

解法：动态规划（分5步）

1状态表示：（一个状态解决不了在定义出另一个状态）

f[i]表示：以i位置为结尾的所有子数组中，最后呈现‘上升’时的最长湍流子数组的长度

g[i]表示：以i位置为结尾的所有子数组中，最后呈现‘下降’时的最长湍流子数组的长度

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

dp表中所有值都初始为1

4填表顺序：从左往右两个表一起填

5返回值：填两个表过程找最长长度

class Solution {
public:int maxTurbulenceSize(vector<int>& arr) {int n=arr.size(),ret=-0x3f3f3f3f;if(n==1) return 1;vector<int> f(n,1),g(n,1);for(int i=1;i<n;i++){if(arr[i-1]<arr[i]) f[i]=g[i-1]+1;else if(arr[i-1]>arr[i]) g[i]=f[i-1]+1;ret=max(ret,max(f[i],g[i]));}return ret;}
};

7单词拆分

oj链接：单词拆分

解法：动态规划（分5步）

1状态表示：

dp[i]表示：在[0,i]位置的字符串是否在词表中

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

为了防止j-1<0：多开一个空间；而且s前多加一个空格（映射处理起来简单）

dp表中所有值都初始为false，

4填表顺序：从左往右填表

5返回值：dp[n]

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {//预处理unordered_set<string> hash;for(auto& word:wordDict) hash.insert(word);// dpint n=s.size();vector<bool> dp(n+1,false);//越界s=" "+s;//一一映射好处理dp[0]=true;for(int i=1;i<=n;i++){for(int j=i;j>0;j--){if(dp[j-1]&&hash.count(s.substr(j,i-j+1))) dp[i]=true;}}return dp[n];}
};

8环绕字符串中唯一的子字符串

oj链接：环绕字符串中唯一的子字符串

解法：动态规划（分5步）

1状态表示：

dp[i]表示：以i位置为结尾的所有子串中，有多少在base中出现过

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

因为每个字符可以单独成立，所以空间都初始化为1

4填表顺序：从左往右填表

5返回值：

dp表进行相加？？

不是的~ 如:【c,a,c】通过上面分析求出来是3，但是答案是2！

我们要进行去重：

相同元素结尾我们去最大值即可（因为最大值包含了较小值的情况！）

a.创建一个大小为26的数组

b.值保存相同元素结尾的最大值

所以正确的返回值：

返回数组里面的和

class Solution {
public:int findSubstringInWraproundString(string s) {int n=s.size(),ret=0;int vis[26]={0};//去重(相同字符)vector<int> dp(n,1);vis[s[0]-'a']=dp[0];for(int i=1;i<n;i++){if(s[i]-s[i-1]==1 || (s[i]=='a'&&s[i-1]=='z')) dp[i]+=dp[i-1];vis[s[i]-'a']=max(vis[s[i]-'a'],dp[i]);}    for(int i=0;i<26;i++) ret+=vis[i];return ret;}
};

五子序列系列

1最长递增子序列

oj链接：最长递增子序列

解法：动态规划（分5步）

1状态表示：

dp[i]表示：以i位置为结尾的所有子序列中，最长子序列的长度

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

因为每个字符可以单独成立，所以空间都初始化为1

4填表顺序：从左往右填表

5返回值：

最长子序列一那个位置为结尾不确定：去dp表的最大值

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n=nums.size(),ret=1;vector<int> dp(n,1);for(int i=1;i<n;i++){for(int j=0;j<i;j++){if(nums[j]<nums[i]) dp[i]=max(dp[i],dp[j]+1);}ret=max(ret,dp[i]);}return ret;}
};

2摆动序列

oj链接：摆动序列

此题与环形子数组的最大和类似：都是一个上升，一个下降要打印两个dp来解决

解法：动态规划（分5步）

1状态表示：

f[i]表示：以i位置为结尾的所有子序列中，最后一个位置是‘上升’状态下最长子序列的长度

g[i]表示：以i位置为结尾的所有子序列中，最后一个位置是‘下降’状态下最长子序列的长度

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

因为每个值可以单独成立，所以空间都初始化为1

4填表顺序：从左往右同时填表

5返回值：

两个表的最大值

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int n=nums.size(),ret=1;vector<int> f(n,1),g(n,1);for(int i=0;i<n;i++){for(int j=0;j<i;j++){if(nums[j]<nums[i]) f[i]=max(f[i],g[j]+1);else if(nums[j]>nums[i]) g[i]=max(g[i],f[j]+1);}ret=max(ret,max(g[i],f[i]));}return ret;}
};

3最长递增子序列的个数

oj链接：最长递增子序列的个数

先来思考这样一个问题：怎么一次遍历得到最大值的个数？

解法：动态规划（分5步）

1状态表示：（有了上面的铺垫，我们就知道一个状态是解决不了问题的）

len[i]表示：以i位置为结尾的所有子序列中，最长子序列的长度

count[i]表示：以i位置为结尾的所有子序列中，最长子序列的个数

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

因为每个值可以单独成立，所以空间都初始化为1

4填表顺序：从左往右两个同时填表

5返回值：

所有最长递增子序列对应的count[i]相加(利用前面的思想)

class Solution {
public:int findNumberOfLIS(vector<int>& nums) {int n=nums.size();vector<int> len(n,1),count(n,1);int retlen=1,retcount=1;//同时进行更新for(int i=1;i<n;i++){for(int j=0;j<i;j++){if(nums[j]<nums[i]){//三种情况if(len[j]+1==len[i]) count[i]+=count[j];//j跟在i后面形成的子序列else if(len[j]+1>len[i]) {len[i]=len[j]+1;count[i]=count[j];//重新计数}//num[j]+1<count[i]不用管}}//利用一次遍历出最大值的个数的算法if(retlen==len[i]) retcount+=count[i];else if(retlen<len[i]) retlen=len[i],retcount=count[i];}return retcount;}
};

4最长数对链

oj链接：最长数对链

在解题之前，我们要先进行预处理：将元素进行排序(以第一个元素排升序)

保证：我们要进行连接的元素都是左边(或者右边)的！

解法：动态规划（分5步）

1状态表示：

dp[i] 以i位置为结尾的所有数对链中，最长数对链的长度

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

因为每个值可以单独成立，所以空间都初始化为1

4填表顺序：从左往右填表

5返回值：

dp表的最大值

class Solution {
public:int findLongestChain(vector<vector<int>>& pairs) {sort(pairs.begin(),pairs.end());int n=pairs.size(),ret=1;vector<int> dp(n,1);for(int i=1;i<n;i++){for(int j=0;j<i;j++){if(pairs[j][1]<pairs[i][0]){dp[i]=(dp[i],dp[j]+1);}ret=max(ret,dp[i]);}}return ret;}
};

5最长定差子序列

oj链接：最长定差子序列

解法：动态规划（分5步）

1状态表示：

dp[i] 以i位置为结尾的所有子序列中，最长定差子序列的长度

2确定状态转移方程(按照题目要求+经验)

与最长递增子序列的思路类似~

3初始化：

因为每个值可以单独成立，所以空间都初始化为1

4填表顺序：从左往右填表

5返回值：

dp表的最大值

//o(N)=n^2 超时
class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {int n=arr.size(),ret=1;vector<int> dp(n,1);for(int i=1;i<n;i++){for(int j=0;j<i;j++){if(arr[i]-arr[j]==difference){dp[i]=max(dp[i],dp[j]+1);}}ret=max(ret,dp[i]);}return ret;}
};

按照上面的分析会发现：数据量太大会超时，所以我们要进行优化：

将a -> dp[i] b -> dp[j] 绑定放在hash表中 (找dp[j]的值就不用在进行遍历了)

所以我们直接在hash表中作动态规划

class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {int n=arr.size(),ret=1;unordered_map<int,int> hash;// dp[i] -> arr[i] dp[j] -> arr[i]-differencehash[arr[0]]=1;for(int i=1;i<n;i++){hash[arr[i]]=hash[arr[i]-difference]+1;ret=max(ret,hash[arr[i]]);}return ret;}
};

6最长的斐波那契子序列的长度

oj链接：最长的斐波那契子序列的长度

解法：动态规划（分5步）

1状态表示：

dp[i] 以i位置为结尾的所有子序列中，最长斐波那契子序列的长度

如果这样定义状态表示：我们是推不出来状态转移方程(不知道长度有多大)

所以换成二维来表示：

dp[i][j] 以i位置和j位置为结尾的所有子序列中，最长斐波那契子序列的长度

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

每个空间都初始化为2(为了不影响填表)

4填表顺序：从上往下填表

5返回值：

dp表的最大值

6优化：

每次要找值所对应的下标要遍历：可以先将元素与下标绑定放在hash表

class Solution {
public:int lenLongestFibSubseq(vector<int>& arr) {int n=arr.size(),ret=2;unordered_map<int,int> hash;//元素/下标for(int i=0;i<n;i++) hash[arr[i]]=i;vector<vector<int>> dp(n,vector<int>(n,2));for(int j=2;j<n;j++)//固定最后一个位置{for(int i=1;i<j;i++)//固定第一个位置{int a=arr[j]-arr[i];if(a<arr[i]&&hash.count(a))//存在且在arr[i]左边{dp[i][j]=dp[hash[a]][i]+1;}ret=max(ret,dp[i][j]);}}return ret==2? 0 : ret;}
};

7最长等差数列

oj链接：最长等差数列

与上题类似~

解法：动态规划（分5步）

1状态表示：

dp[i] 以i位置为结尾的所有子序列中，最长等差数列的长度

如果这样定义状态表示：我们是推不出来状态转移方程(不知道长度有多大)

所以换成二维来表示：

dp[i][j] 以i位置和j位置为结尾的所有子序列中，最长等差数列的长度

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

每个空间都初始化为2(为了不影响填表) dp[0][0] = 2？不是1吗？

因为填表要i<j，所以这些位置用不到~

4填表顺序：先固定倒数第二个位置，枚举倒数第一个位置

5返回值：

dp表的最大值

6优化：

1.在填表前将元素与下标数组进行绑定放在hash表中（三层for循环不推荐）

2.变填表变把元素与下标绑定放在hash表中（代码实现是这种）

class Solution {
public:int longestArithSeqLength(vector<int>& nums) {int n=nums.size(),ret=2;vector<vector<int>> dp(n,vector<int>(n,2));unordered_map<int,int> hash;//值->下标for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){int tmp=2*nums[i]-nums[j];if(hash.count(tmp))//tmp<ihash表保证了{dp[i][j]=dp[hash[tmp]][i]+1;}ret=max(ret,dp[i][j]);}hash[nums[i]]=i;//前提:先固定倒数第二个数,在进行枚举(保证tmp的下标离i是最近的)}return ret;}
};

8等差数列划分

oj链接：等差数列划分

与上题类似~

解法：动态规划（分5步）

1状态表示：

dp[i] 以i位置为结尾的所有子序列中，有多少个等差数列

如果这样定义状态表示：我们是推不出来状态转移方程(不知道长度有多大)

所以换成二维来表示：

dp[i][j] 以i位置和j位置为结尾的所有子序列中，有多少个等差数列

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

都为0(开始时不存在)

4填表顺序：固定倒数第二个位置，枚举倒数第一个位置

5返回值：

dp表中所有值相加

6优化：

1.在填表前将元素与下标数组进行绑定放在hash表中

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {int n=nums.size(),ret=0;vector<vector<int>> dp(n,vector<int>(n));unordered_map<long long,vector<int>> hash;for(int i=0;i<n;i++) hash[nums[i]].push_back(i);//一个元素可能有多个,对应多个下标for(int i=1;i<n;i++){for(int j=i+1;j<n;j++){long long tmp=(long long)2*nums[i]-nums[j];if(hash.count(tmp)){for(auto& pos:hash[tmp]){if(pos<i) dp[i][j]+=dp[pos][i]+1;//tmp,i,j组成新的等差数列}}ret+=dp[i][j];}}return ret;}
};

六回文串问题

1回文子串

oj链接：回文子串

解法：动态规划（分5步）

1状态表示：

dp[i][j] 表示以i位置为起点，j位置为结尾，组成的子串是否是回文子串(i<=j)

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

空间都初始化为false(边界问题不用处理了，如：[0][0],[1][0]在确定状态转移方程时特判过了)

4填表顺序：从下往上(dp[i][j] -> dp[i+1][j-1] 从表下边来的)

5返回值：

dp表为true进行统计

注：这样ac的时间复杂度O(N)=n^2很高，但这个思路能解决相关问题的hard题！！

class Solution {
public:int countSubstrings(string s) {int n=s.size(),ret=0;vector<vector<bool>> dp(n,vector<bool>(n,false));for(int i=n-1;i>=0;i--){for(int j=i;j<n;j++){if(s[i]==s[j]){if(i==j||i+1==j||dp[i+1][j-1]) dp[i][j]=true;}}}for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(dp[i][j]) ret++;}}return ret;}
};

2最长回文子串

oj链接：最长回文子串

a先建表把回文子串的信息保存在表中（上面的思路）

用表中的两层循环遍历找出最长子串不就是很容易的事吗！

class Solution {
public:string longestPalindrome(string s) {int n=s.size();vector<vector<bool>> dp(n,vector<bool>(n));//以i为开头，j为结尾的回文子串for(int i=n-1;i>=0;i--){for(int j=i;j<=n;j++)//要保证i<=j{if(s[i]==s[j]){if(i==j) dp[i][j]=true;else if(i+1==j) dp[i][j]=true;else if(dp[i+1][j-1]) dp[i][j]=true;}}}int begin=0,end=0;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(dp[i][j]){if(j-i+1>end-begin+1){begin=i;end=j;}}}}return s.substr(begin,end-begin+1);}
};

3分割回文串IV

oj链接：分割回文串 IV

还是同样套路：先建表把回文串的信息保存在表中

再循环遍历判断字符串能否被分成两段(只用两层循环时要注意越界问题！)

class Solution {
public:bool checkPartitioning(string s) {int n=s.size();vector<vector<bool>> dp(n,vector<bool>(n));//以i为开头，j为结尾的回文子串for(int i=n-1;i>=0;i--){for(int j=i;j<=n;j++)//要保证i<=j{if(s[i]==s[j]){if(i==j) dp[i][j]=true;else if(i+1==j) dp[i][j]=true;else if(dp[i+1][j-1]) dp[i][j]=true;}}}for(int i=1;i<n;i++)//从0开始会越界 -> i-1{for(int j=i;j<n-1;j++)//n-1结束会越界 -> j+1{if(dp[0][i-1]&&dp[i][j]&&dp[j+1][n-1]) return true;}}return false;}
};

4分割回文串 II

oj链接： LCR 094. 分割回文串 II - 力扣（LeetCode）

解法：动态规划（分5步）

1状态表示：

dp[i] 表示以i结尾的子串中，最少的分割次数

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

都初始化为最大值：防止影响填表

4填表顺序：

从左往右

5返回值：

dp表的最后一个值

class Solution {
public:int minCut(string s) {int n=s.size();vector<vector<bool>> vis(n,vector<bool>(n,false));for(int i=n-1;i>=0;i--){for(int j=i;j<n;j++){if(s[i]==s[j]){if(i==j||i+1==j||vis[i+1][j-1]) vis[i][j]=true;}}}vector<int> dp(n,INT_MAX);for(int i=0;i<n;i++){if(vis[0][i]) dp[i]=0;else{for(int j=0;j<=i;j++){if(vis[j][i]) dp[i]=min(dp[i],dp[j-1]+1);}}}return dp[n-1];}
};

5最长回文子序列

oj链接：最长回文子序列

解法：动态规划（分5步）

1状态表示：

(老套路)dp[i] 表示以i结尾的子序列中，最长回文子序列的长度

我们会发现推不了状态转移方程：因为不知道回文子序列长什么样！

所以我们要重新定义状态表示

dp[i][j] 表示在[i][j]区间的字符串中，最长回文子序列的长度

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

由于分的情况很细，第一行第一个位置和最后一行最后一个位置(可能越界)特判过了

所以不用初始化

4填表顺序：

从下到上，从左往右

5返回值：

dp[0][n]

class Solution {
public:int longestPalindromeSubseq(string s) {int n=s.size();vector<vector<int>> dp(n,vector<int>(n));for(int i=n-1;i>=0;i--){for(int j=i;j<n;j++){if(s[i]==s[j]){if(i==j) dp[i][j]=1;else if(i+1==j) dp[i][j]=2;else dp[i][j]=dp[i+1][j-1]+2;}else{dp[i][j]=max(dp[i][j-1],dp[i+1][j]);}}}return dp[0][n-1];}
};

6让字符串成为回文串的最少插入次数

oj链接：让字符串成为回文串的最少插入次数

此题思路与上题类似！

解法：动态规划（分5步）

1状态表示：

(老套路)dp[i] 表示以i结尾的子序列中，成为回文串的最少插入次数

我们会发现推不了状态转移方程：因为不知道回文子序列长什么样！

所以我们要重新定义状态表示

dp[i][j] 表示在[i][j]区间的字符串中，成为回文串的最少插入次数

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

由于分的情况很细，第一行第一个位置和最后一行最后一个位置(可能越界)特判过了

所以不用初始化

4填表顺序：

从下到上，从左往右

5返回值：

dp[0][n-1]

class Solution {
public:int minInsertions(string s) {int n=s.size();vector<vector<int>> dp(n,vector<int>(n,0x3f3f3f3f));for(int i=n-1;i>=0;i--){for(int j=i;j<n;j++){if(s[i]==s[j]){if(i==j||i+1==j) dp[i][j]=0;else dp[i][j]=dp[i+1][j-1];}else dp[i][j]=min(dp[i+1][j]+1,dp[i][j-1]+1);}}return dp[0][n-1];}
};

七两个数组的dp问题

1最长公共子序列

oj链接：最长公共子序列

解法：动态规划（分5步）

1状态表示：

dp[i][j] 表示在s1[0,i]区间 s2[0,j]区间的所有子序列中，最长子序列的长度

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

在这里引入空串（有研究意义）

为了不越界，多开一行一列：

第一行表示s1是空串的情况，第一列表示s2是空串的情况(初始化为0)

s1=" "+s1 s2=" "+s2 --> 不用加1进行映射

4填表顺序：

从上到下，从左往右

5返回值：

dp[n][m]

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int n=text1.size(),m=text2.size();vector<vector<int>> dp(n+1,vector<int>(m+1));//空串进行初始化text1=" "+text1;//空串进行映射text2=" "+text2;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(text1[i]==text2[j]) dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],max(dp[i][j-1],dp[i-1][j-1]));//重复不管}}return dp[n][m];}
};

2通配符匹配

oj链接：通配符匹配

解法：动态规划（分5步）

1状态表示：

dp[i][j] 表示在 s[0,i]区间内的子串是否能被 p[0,j]区间内的子串匹配

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

s1=" "+s1 s2=" "+s2 --> 不用加1进行映射

在这里引入空串（有研究意义）

为了不越界，多开一行一列：

第一行表示s是空串的情况，第一列表示p是空串的情况

s是空串的情况下p串可能有*来表示空串：从左到右循环一遍遇到*dp填true,其它情况都是false(即使后面又有*)

4填表顺序：

从上到下，从左往右

5返回值：

dp[n][m]

将第三种情况进行优化


class Solution {
public:bool isMatch(string s, string p) {int n=s.size(),m=p.size();vector<vector<bool>> dp(n+1,vector<bool>(m+1));s=" "+s,p=" "+p;dp[0][0]=true;for(int j=1;j<=m;j++){if(p[j]=='*') dp[0][j]=true;else break;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(p[j]=='*'){dp[i][j]=dp[i][j-1];//一个一个分析for(int k=i-1;k>=0;k--){dp[i][j]=dp[i][j]||dp[k][j-1];}}else{if((p[j]==s[i]||p[j]=='?')&&dp[i-1][j-1]) dp[i][j]=true;}}}return dp[n][m];}
};class Solution {
public:bool isMatch(string s, string p) {int n=s.size(),m=p.size();vector<vector<bool>> dp(n+1,vector<bool>(m+1));s=" "+s,p=" "+p;dp[0][0]=true;for(int j=1;j<=m;j++){if(p[j]!='*') break;else dp[0][j]=true;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(p[j]=='*'){dp[i][j]=dp[i][j-1]||dp[i-1][j];//dp[i][j] = dp[i][j-1]||dp[i-1][j-1]||dp[i-2][j-1]||dp[i-3][j-1]...//dp[i-1][j] = dp[i-1][j-1]||dp[i-2][j-2]||dp[i-3][j-1]...}else{if((p[j]==s[i]||p[j]=='?')&&dp[i-1][j-1]) dp[i][j]=true;}}}return dp[n][m];}
};

3正则表达式匹配

oj链接：正则表达式匹配

题目解析是要注意：题目保证*前是有效字符；*与前面字符结合可以是空串！

解法：动态规划（分5步）

1状态表示：

dp[i][j] 表示在 s[0,i]区间内的子串是否能被 p[0,j]区间内的子串匹配

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

s1=" "+s1 s2=" "+s2 --> 不用加1进行映射

在这里引入空串（有研究意义）

为了不越界，多开一行一列：

第一行表示s是空串的情况，第一列表示p是空串的情况

s是空串的情况下p串可能有*来表示空串：

下标为i=2开始(下一个i+=2):从左到右循环一遍遇到*dp填true,否则都是false(即使后面又有*)

4填表顺序：

从上到下，从左往右

5返回值：

dp[n][m]

class Solution {
public:bool isMatch(string s, string p) {int n=s.size(),m=p.size();s=" "+s,p=" "+p;vector<vector<bool>> dp(n+1,vector<bool>(m+1));dp[0][0]=true;for(int j=2;j<=m;j+=2){if(p[j]=='*') dp[0][j]=true;else break;}for(int i=1;i<=n;i++){class Solution {
public:bool isMatch(string s, string p) {int n=s.size(),m=p.size();vector<vector<bool>> dp(n+1,vector<bool>(m+1,false));s=" "+s;p=" "+p;dp[0][0]=true;for(int j=2;j<=m;j+=2){if(p[j]=='*') dp[0][j]=true;else break;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(p[j]==s[i]||p[j]=='.') dp[i][j]=dp[i-1][j-1];else if(p[j]=='*'){if(p[j-1]=='.'){dp[i][j]=dp[i][j-2]||dp[i-1][j];}else{dp[i][j]=dp[i][j-2];if(p[j-1]==s[i]) dp[i][j]=dp[i][j]||dp[i-1][j];}}}}return dp[n][m];}
};for(int j=1;j<=m;j++){if(p[j]=='*'){dp[i][j]=dp[i][j-2]||(p[j-1]==s[i]||p[j-1]=='.')&&dp[i-1][j];}else{dp[i][j]=(s[i]==p[j]||p[j]=='.')&&dp[i-1][j-1];}}}return dp[n][m];}
};

4交错字符串

oj链接：交错字符串

解法：动态规划（分5步）

1状态表示：

dp[i][j] 表示在 s1[0,i] s2[0,j]是否能够交错拼成s3

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

s1=" "+s1 s2=" "+s2 --> 不用加1进行映射

在这里引入空串（有研究意义）

为了不越界，多开一行一列：

第一行表示s1是空串的情况，第一列表示s2是空串的情况

例如：s1是空串时，s2与s3字符进行比较，相等为true：发现不相等就为false(停止下去)

4填表顺序：

从上到下，从左往右

5返回值：

dp[n][m]

class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int n=s1.size(),m=s2.size();if(n+m!=s3.size()) return false;vector<vector<bool>> dp(n+1,vector<bool>(m+1,false));s1=" "+s1,s2=" "+s2,s3=" "+s3;dp[0][0]=true;for(int i=1;i<=n;i++){if(s1[i]==s3[i]) dp[i][0]=true;else break;}for(int j=1;j<=m;j++){if(s2[j]==s3[j]) dp[0][j]=true;else break;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s1[i]==s3[i+j]&&dp[i-1][j]) dp[i][j]=true;if(s2[j]==s3[i+j]&&dp[i][j-1]) dp[i][j]=true;}}return dp[n][m];}
};

5两个字符串的最小ASCLL删除和

oj链接：两个字符串的最小ASCII删除和

在求解之前，可以先把这道题转化成：求两个字符串的相同子序列的最大ASCLL和

解法：动态规划（分5步）

1状态表示：

dp[i][j] 表示在 s1[0,i] s2[0,j]中所有子序列中，相同字符串的最大ASCLL和

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

不用往前面加空格（防止干扰），下标-1来映射即可

4填表顺序：

从上到下，从左往右

5返回值：

求出s1,s2的ASCLL和sum

sum - dp[n][m] - dp[n][m]

class Solution {
public:int minimumDeleteSum(string s1, string s2) {int n=s1.size(),m=s2.size();vector<vector<int>> dp(n+1,vector<int>(m+1));//s1=" "+s1,s2=" "+s2;//防止加到" "的值for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+s1[i-1];dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i][j-1])); }}int sum=0;for(auto& s:s1) sum+=s;for(auto& s:s2) sum+=s;return sum-2*dp[n][m];}
};

6最长重复子数组

oj链接：最长重复子数组

在求解之前我们要注意：要求的是连续重复的最长子数组不是子序列！

所以状态表示就不能用 以某段区间来分析状态转移方程

解法：动态规划（分5步）

1状态表示：

dp[i][j] 表示在 nums1中以i位置为结尾的所有子数组num2中以j位置为结尾的所有子数组中最长重复子数组的长度

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

加一行加一列即可

4填表顺序：

从上到下，从左往右

5返回值：

dp表的最大值(以哪个位置为结尾的子数组最长不知道)

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {int n=nums1.size(),m=nums2.size(),ret=0;vector<vector<int>> dp(n+1,vector<int>(m+1));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(nums1[i-1]==nums2[j-1]) dp[i][j]=dp[i-1][j-1]+1;ret=max(ret,dp[i][j]);}}return ret;}
};

八01背包问题

0[模板]01背包

oj链接：[模板]01背包

第一个问

解法：动态规划（分5步）

1状态表示

dp[i][j] 表示从i个数里选，总体积不超过j，所有选法中的最大价值

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

加一行加一列即可

4填表顺序：

从上到下，从左往右

5返回值：

dp[n][V]

第二个问

解法：动态规划（分5步）

1状态表示

dp[i][j] 表示从i个数里选，总提交恰好等于j，所有选法中的最大价值

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

加一行加一列 dp[0][0]=0(不选物品凑成体积为0的最大价值)

接着第一行其余的数就全部初始化成-1(表示不存在)

4填表顺序：

从上到下，从左往右

5返回值：

dp[n][V]==-1?0:dp[n][V]

#include <iostream>
#include <cstring>
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 =0; 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 =0; 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;
}

优化

利用滚动数组空间上的优化

代码实现：

a删除所有横坐标

b修改j的遍历顺序

#include <iostream>
#include <cstring>
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]=dp[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--) // 修改遍历顺序{//dp[j] = dp[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;
}

1分割等和子集

oj链接：分割等和子集

我们可以先对题目进行转化：在数组中挑一些数，使得和等于数组相加和的一半！

所以问题就转化为01背包问题啦！

解法：动态规划（分5步）

1状态表示

dp[i][j] 表示从i个数里选，所有选法中能否凑成j这个数

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

加一行加一列即可 初始化dp[0][0]=ture即可

4填表顺序：

从上到下，从左往右

5返回值：

dp[n][sum/2]

class Solution {
public:bool canPartition(vector<int>& nums) {//挑一些数使得结果是否等于sum/2int sum=reduce(nums.begin(),nums.end()),n=nums.size();if(sum%2!=0) return false;vector<vector<bool>> dp(n+1,vector<bool>(sum/2+1,false));dp[0][0]=true;for(int i=1;i<=n;i++){for(int j=1;j<=sum/2;j++){dp[i][j]=dp[i-1][j];if(j-nums[i-1]>=0) dp[i][j]=dp[i][j]||dp[i-1][j-nums[i-1]];}}return dp[n][sum/2];}
};class Solution {
public:bool canPartition(vector<int>& nums) {//挑一些数使得结果是否等于sum/2int sum=reduce(nums.begin(),nums.end()),n=nums.size();if(sum%2!=0) return false;vector<bool> dp(sum/2+1,false);dp[0]=true;for(int i=1;i<=n;i++){for(int j=sum/2;j>=nums[i-1];j--){dp[j]=dp[j]||dp[j-nums[i-1]];}}return dp[sum/2];}
};

2目标和

oj链接：目标和

求解之前先来计算

这样问题就转为：选择一些数使得和等于a！也就是01背包问题

解法：动态规划（分5步）

1状态表示

dp[i][j] 表示从i个数里选，所有选法中能否凑成j这个数共有多少种选法

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

加一行加一列即可 初始化dp[0][0]=1即可

4填表顺序：

从上到下，从左往右

5返回值：

dp[n][a/2]

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {// a+b=sum a-b=t // a=(sum+t)/2是一个确定的值//选一些数凑成a的选法int sum=reduce(nums.begin(),nums.end());int aim=(sum+target)/2,n=nums.size();if(aim<0||(sum+target)%2!=0) return 0;//细节的边界处理vector<vector<int>> dp(n+1,vector<int>(aim+1));dp[0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<=aim;j++){dp[i][j]=dp[i-1][j];if(j-nums[i-1]>=0) dp[i][j]+=dp[i-1][j-nums[i-1]];}}return dp[n][aim];}
};class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {// a+b=sum a-b=t // a=(sum+t)/2是一个确定的值//选一些数凑成a的选法int sum=reduce(nums.begin(),nums.end());int aim=(sum+target)/2,n=nums.size();if(aim<0||(sum+target)%2!=0) return 0;//细节的边界处理vector<int> dp(aim+1);dp[0]=1;for(int i=1;i<=n;i++){for(int j=aim;j>=nums[i-1];j--){dp[j]+=dp[j-nums[i-1]];}}return dp[aim];}
};

3最后一块石头的重量 II

oj链接：最后一块石头的重量 II

这样问题就转为：选择一些数使得和等于sum/2！也就是01背包问题

解法：动态规划（分5步）

1状态表示

dp[i][j] 表示从i个数里选，所有选法中能否凑成j这个数的最大和

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

加一行加一列即可

4填表顺序：

从上到下，从左往右

5返回值：

sum-2*dp[n][sum/2] 或者是 abs(dp[n][sum/2]-(sum-dp[n][sum/2]))

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {//sum/2问题int sum=reduce(stones.begin(),stones.end()),n=stones.size();vector<vector<int>> dp(n+1,vector<int>(sum/2+1));for(int i=1;i<=n;i++){for(int j=0;j<=sum/2;j++){dp[i][j]=dp[i-1][j];if(j-stones[i-1]>=0) dp[i][j]=max(dp[i][j],dp[i-1][j-stones[i-1]]+stones[i-1]);}}return sum-2*dp[n][sum/2];//a=dp[n][sum/2] b=sum-a=sum-dp[n][sum/2]求两者之差}
};class Solution {
public:int lastStoneWeightII(vector<int>& stones) {//sum/2问题int sum=reduce(stones.begin(),stones.end()),n=stones.size();vector<int> dp(sum/2+1);for(int i=1;i<=n;i++){for(int j=sum/2;j>=stones[i-1];j--){dp[j]=max(dp[j],dp[j-stones[i-1]]+stones[i-1]);}}return sum-2*dp[sum/2];//a=dp[n][sum/2] b=sum-a=sum-dp[n][sum/2]求两者之差}
};

九完全背包问题

0[模板]完全背包

oj链接：[模板]完全背包

第一问

解法：动态规划（分5步）

1状态表示

dp[i][j] 表示从i个数里选，总体积不超过j，所有的选法中最大价值

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

加一行加一列

4填表顺序：

从上到下，从左往右

5返回值：

dp[n][V

第二个问

解法：动态规划（分5步）

1状态表示

dp[i][j] 表示从i个数里选，总体积恰好等于j，所有选法中的最大价值

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

加一行加一列 dp[0][0]=0(不选物品凑成体积为0的最大价值)

接着第一行其余的数就全部初始化成-1(表示不存在)

4填表顺序：

从上到下，从左往右

5返回值：

dp[n][V]==-1?0:dp[n][V]

#include <iostream>
#include <cstring>
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 =0; 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 =0; 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;
}

#include <iostream>
#include <cstring>
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;
}

1零钱兑换

oj链接：零钱兑换

解法：动态规划（分5步）

1状态表示

dp[i][j] 表示从i个数里选，总提交恰好等于j，所有选法中的最大金额

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

加一行加一列，dp[0][0] = 0 （不用选金额就是0）

都初始化为0x3f3f3f3f（防止干扰填表）

4填表顺序：

从上到下，从左往右

5返回值：

dp[n][amount]

class Solution
{
public:int coinChange(vector<int> &coins, int amount){int n = coins.size();vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0x3f3f3f3f));dp[0][0] = 0;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] >= 0)dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);}}return dp[n][amount] == 0x3f3f3f3f ? -1 : dp[n][amount];}
};class Solution
{
public:int coinChange(vector<int> &coins, int amount){int n = coins.size();vector<int> dp(amount + 1, 0x3f3f3f3f);dp[0] = 0;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] == 0x3f3f3f3f ? -1 : dp[amount];}
};

2零钱兑换Ⅱ

oj链接：零钱兑换 II

解法：动态规划（分5步）

1状态表示

dp[i][j] 表示从i个数里选，总提交恰好等于j，所有选法中的和

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

加一行加一列，dp[0][0] = 1 （不用选金额等于0就是一种）

4填表顺序：

从上到下，从左往右

5返回值：

dp[n][amount]

class Solution
{
public:int change(int amount, vector<int> &coins){// if(amount==4681) return 0;bool tmp = true;for (auto &e : coins){if (e % 2 != 0)tmp = false;}if (tmp && amount % 2 != 0)return 0;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];}
};class Solution
{
public:int change(int amount, vector<int> &coins){// if(amount==4681) return 0;bool tmp = true;for (auto &e : coins){if (e % 2 != 0)tmp = false;}if (tmp && amount % 2 != 0)return 0;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];}
};

3完全平方数

oj链接：完全平方数

解法：动态规划（分5步）

1状态表示

dp[i][j] 表示从i个完全平方数里选，总和恰好等于j，所有选法中的最少数量

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

加一行加一列，dp[0][0] = 0 （不用选就等于0）

其余都初始化成0x3f3f3f3f(防止干扰)

4填表顺序：

从上到下，从左往右

5返回值：

dp[sqrt(n)][n]

class Solution
{
public:int numSquares(int n){vector<vector<int>> dp(sqrt(n) + 1, vector<int>(n + 1, 0x3f3f3f3f));dp[0][0] = 0;for (int i = 1; i <= sqrt(n); 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[sqrt(n)][n] >= 0x3f3f3f3f ? 0 : dp[sqrt(n)][n];}
};class Solution
{
public:int numSquares(int n){vector<int> dp(n + 1, 0x3f3f3f3f);dp[0] = 0;for (int i = 1; i <= n; i++){for (int j = i * i; j <= n; j++){dp[j] = min(dp[j], dp[j - i * i] + 1);}}return dp[n] >= 0x3f3f3f3f ? 0 : dp[n];}
};

十二维费用的背包问题

1一和零

oj链接：一和零

这题其实也就是01背包问题多加一维：本质还是01背包问题！

解法：动态规划（分5步）

1状态表示

dp[i][j][k] 表示从i个str里选，总和0数不超过m，总和1数不超过n，所有选法中的最大长度

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

不用初始化(dp[0][0][0]=0即可)

4填表顺序：

从上到下，从左往右

5返回值：

dp[a][m][n]

class Solution
{
public:int findMaxForm(vector<string> &strs, int m, int n){int a = strs.size();vector<vector<vector<int>>> dp(a + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));for (int i = 1; i <= a; i++){string str = strs[i - 1];int zero = 0, one = 0;for (auto &s : str){if (s == '0')zero++;elseone++;}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 >= zero && k >= one)dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - zero][k - one] + 1);}}}return dp[a][m][n];}
};class Solution
{
public:int findMaxForm(vector<string> &strs, int m, int n){int a = strs.size();vector<vector<vector<int>>> dp(a + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));for (int i = 1; i <= a; i++){string str = strs[i - 1];int zero = 0, one = 0;for (auto &s : str){if (s == '0')zero++;elseone++;}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 >= zero && k >= one)dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - zero][k - one] + 1);}}}return dp[a][m][n];}
};

2盈利计划

oj链接：盈利计划

解法：动态规划（分5步）

1状态表示

dp[i][j][k] 表示从i个计划里选，总人数不超过n，总利润至少是profit，共有多少种选法

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

dp[0][j][0] = 1 不用选计划总利润为0的选法(0<= j <= n)

4填表顺序：

从上到下，从左往右

5返回值：

dp[a][m][n]

class Solution
{
public:int profitableSchemes(int n, int minProfit, vector<int> &group, vector<int> &profit){const int mod = 1e9 + 7;int a = group.size();vector<vector<vector<int>>> dp(a + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1)));for (int j = 0; j <= n; j++)dp[0][j][0] = 1;for (int i = 1; i <= a; 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])]; // k-profit[i-1]<0有意义dp[i][j][k] %= mod;}}}return dp[a][n][minProfit];}
};class Solution
{
public:int profitableSchemes(int n, int minProfit, vector<int> &group, vector<int> &profit){const int mod = 1e9 + 7;int a = group.size();vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1));for (int j = 0; j <= n; j++)dp[j][0] = 1;for (int i = 1; i <= a; i++){for (int j = n; j >= group[i - 1]; j--){for (int k = 0; k <= minProfit; k++){if (j >= group[i - 1])dp[j][k] += dp[j - group[i - 1]][max(0, k - profit[i - 1])]; // k-profit[i-1]<0有意义dp[j][k] %= mod;}}}return dp[n][minProfit];}
};

十三似包非包

1组合总和Ⅳ

oj链接：排列总和 Ⅳ

注意：该题是求出排列总和，不是我们数学上的组合总和！

而背包问题是来求组合的：所以此题不用用背包问题思路来解决~

解法：动态规划（分5步）

1状态表示（发现重复子问题后抽象出来一个状态表示）

dp[i]表示凑成和为i 一共有多少种排列数

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

dp[0] = 1

4填表顺序：

从左往右

5返回值：

dp[target]

class Solution
{
public:int combinationSum4(vector<int> &nums, int target){int n = nums.size();vector<double> dp(target + 1);dp[0] = 1;for (int i = 1; i <= target; i++){for (auto e : nums){if (i >= e)dp[i] += dp[i - e];}}return dp[target];}
};

十四卡特兰数

1不同的二叉搜索树

oj链接：不同的二叉搜索树

解法：动态规划（分5步）

1状态表示（发现重复子问题后抽象出来一个状态表示）

dp[i]表示节点数为i 一共有多少个二叉搜索树

2确定状态转移方程(按照题目要求+经验)

画图分析

3初始化：

dp[0] = 1

4填表顺序：

从左往右

5返回值：

dp[n]

class Solution
{
public:int numTrees(int n){vector<int> dp(n + 1); // 组成总和为i的节点的个数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];}
};