目录 1.动态规划问题分类 2.线性DP         一维数组         二维坐标系         LIS(最长上升子序列)         LCS(最长公共子序列)         01背包         完全背包         多重背包

                               

1.动态规划问题分类

2.线性DP

2.1一维数组

思路： 一个连续子数组一定要以一个数作为结尾，那么我们可以将状态定义成如下：

dp[i]：表示以 nums[i] 结尾的连续子数组的最大和。

那么想得到dp[i],nums[i]我们是一定会选取的，根据dp[i-1]的大小我们分为两种情况

dp[i-1]大于0的话：dp[i]=dp[i-1]+nums[i] dp[i-1]小于0的话：dp[i]=nums[i](加上dp[i-1]反而还没有一定会选取的nums[i]大)

C++代码：

class Solution { public: int maxSubArray(vector<int>& nums) { if(nums.empty()) return 0; vector<int> dp(nums.size(),0); dp[0]=nums[0]; int max=nums[0]; for(int i=1;i<nums.size();i++) { if(dp[i-1]>=0) { dp[i]=dp[i-1]+nums[i]; if(dp[i]>max) max=dp[i]; } else { dp[i]=nums[i]; if(dp[i]>max) max=dp[i]; } } return max; } };

思路：

我们定义dp[i]为偷盗至第i个房子时，所能获取的最大利益。那我们可以想到，由于不可以在相邻的房屋闯入，所以 至i房屋可盗窃的最大值，要么就是至 i-1 房屋可盗窃的最大值，要么就是至 i-2 房屋可盗窃的最大值加上当前房屋的值，二者之间取最大值。即：

dp[i] = max(dp[i-2]+nums[i], dp[i-1])

这里要注意对于第二间房间偷盗的最大金额为前两间房间所有的金额的最大值

C++代码：

class Solution{ public: int rob(vector<int>& nums) { if(nums.empty()) return 0; if(nums.size()>=2) nums[1]=max(nums[0],nums[1]); for(int i=2;i<nums.size();i++) nums[i]=max(nums[i]+nums[i-2],nums[i-1]); return nums[nums.size()-1]; } };

2.2二维数组

思路：

我们定义d[i][j]：

dp[i][j] : 表示包含第i行j列元素的最小路径和

无论最后的路径是哪一条，它一定要经过最顶上的元素，即[0,0]。所以我们需要对dp[0][0]进行初始化。

dp[0][0] = [0][0]位置所在的元素值

每一行最左边的元素只能从自己头顶而来： dp[i][j]=dp[i-1][j]+triangle[i][j]; 每一行最右边的元素只能从自己左上角而来： dp[i][j]=dp[i-1][j-1]+triangle[i][j]; 其余的元素是从左边或者头顶元素两种途径而言(既然是要求最小，那么取两种途径的最小值)： dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+triangle[i][j];

C++代码：

class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { int size=triangle.size(); int dp[size][size]; memset(dp,0,sizeof(dp)); dp[0][0]=triangle[0][0]; for(int i=1;i<size;i++) { for(int j=0;j<=i;j++) { if(j==0) dp[i][j]=dp[i-1][j]+triangle[i][j]; else if(j==i) dp[i][j]=dp[i-1][j-1]+triangle[i][j]; else dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+triangle[i][j]; } } int min=INT_MAX; for(int i=0;i<size;i++) { if(min>dp[size-1][i]) min=dp[size-1][i]; } return min; } };

思路： 本题可以不使用任何额外的空间就能解答

我们先分析第一行，我们在第一行从左往右扫描，如果是0那么就有1种走法就把这个位置的元素变成1，如果有一个位置有障碍物，那么包含这个位置在内，障碍物后边元素的走法都是0。这可以用标志位在程序中实现，定义一个flag=0，如果找到一个障碍物后标志位置1。

我们没扫描元素之前，元素的0和1是代表有无障碍物，扫描之后代表的是这个位置有多少种走法

我们再分析第一列，同样的第一列只要有1个位置是障碍物，包含障碍物在内走法都是0

对于其他的，是障碍物，那么障碍物所在位置的走法一定是0，对于不是障碍物，那么走法是左边元素和上边元素的和(即使左边和上边的元素是障碍物也无所谓，因为障碍物的走法是0)

C++代码实现：

class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m=obstacleGrid.size(); int n=obstacleGrid[0].size(); int flag=0; int f=0; if(obstacleGrid[0][0]) return 0; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(i==0&&j!=0&&obstacleGrid[i][j]==0&&flag==0) obstacleGrid[i][j]=1; else if(i==0&&j!=0&&obstacleGrid[i][j]==1) { obstacleGrid[i][j]=0; flag=1; } else if(j==0&&obstacleGrid[i][j]==0&&f==0) obstacleGrid[i][j]=1; else if(j==0&&obstacleGrid[i][j]==1) { obstacleGrid[i][j]=0; f=1; } else { if(obstacleGrid[i][j]==0&&i>0&&j>0) obstacleGrid[i][j]=obstacleGrid[i-1][j]+obstacleGrid[i][j-1]; else obstacleGrid[i][j]=0; } } } return obstacleGrid[m-1][n-1]; } };

2.3LIS

本题我们可以按照w从小到大排序，w相同的按照h从大到小(这样整个问题就变成了求排序后h的最大增长子序列)，再用动态规划求解

C++代码：

bool com(vector<int> &a,vector<int> &b){ if(a[0]>b[0]) return false; else if(a[0]<b[0]) return true; else { if(a[1]<b[1]) return false; else return true; } } class Solution { public: int maxEnvelopes(vector<vector<int>>& envelopes) { if(!envelopes.size()) return 0; sort(envelopes.begin(),envelopes.end(),com); vector<int> res(envelopes.size(),1); vector<int> vec; int max1=0; for(int i=0;i<envelopes.size();i++) vec.push_back(envelopes[i][1]); for(int i=0;i<vec.size();i++) { for(int j=0;j<i;j++) { if(vec[i]>vec[j]) res[i]= max(res[i],res[j]+1); } if(max1<res[i]) max1=res[i]; } return max1; } };

2.4LCS

子序列类型的问题，穷举出所有可能的结果都不容易，而动态规划算法做的就是穷举 + 剪枝，它俩天生一对儿。所以可以说只要涉及子序列问题，十有八九都需要动态规划来解决。

本题我们可以使用二维数组来做dp[i][j]的意思就是text1的前i个字符与text2的前j个字符的最大公共序列

因此可以得出： 现在对比的这两个字符不相同的，那么我们要取它的「要么是text1往前退一格，要么是text2往前退一格，两个的最大值」 dp[i + 1][j + 1] = Math.max(dp[i+1][j], dp[i][j+1]);

对比的两个字符相同，去找它们前面各退一格的值加1即可：dp[i+1][j+1] = dp[i][j] + 1;

class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m=text1.size(),n=text2.size(); int dp[m+1][n+1]; memset(dp,0,sizeof(dp)); for (int i=1;i<=m;i++) { for (int j=1;j<=n;j++) { if (text1[i-1]==text2[j-1]) { dp[i][j]=dp[i-1][j-1]+1; } else { dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } } return dp[m][n]; } };

2.3 01背包