参考内容

 https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/

https://leetcode-cn.com/problems/fibonacci-number/solution/dong-tai-gui-hua-tao-lu-xiang-jie-by-labuladong/

https://leetcode-cn.com/circle/article/NfHhXD/

https://leetcode-cn.com/circle/article/2Xxlw3/

非常感谢上述内容提供者无私的分享

目录

参考内容

动态规划做题一般步骤

1、状态（dp）

2、状态转移方程

3、初始化

4、输出

1. 数塔

2. 背包

3.路径

4骰子

5约束

6股票问题

6区间 DP

7最长子序列/子字符串

8回文子序列/子字符串

动态规划做题一般步骤

1、状态（dp）

状态的定义，先尝试「题目问什么，就把什么设置为状态」；
然后思考「状态如何转移」，如果「状态转移方程」不容易得到，尝试修改定义，目的依然是为了方便得到「状态转移方程」。
「状态转移方程」是原始问题的不同规模的子问题的联系。即大问题的最优解如何由小问题的最优解得到。

对状态的定义，在不同类型的题目中，各不相同，有些题目dp维数低，有些题目中使用高维数dp

动态规划是非常灵活的一种思维模式，很难像其他算法一样找到通用的模板，在同一类型题目中，dp的设置比较相似，如果再次遇到相似的问题，可以进行参考。

2、状态转移方程

状态转移方程是非常重要的，是动态规划的核心，也是难点；

常见的推导技巧是：分类讨论。即：对状态空间进行分类；

归纳「状态转移方程」是一个很灵活的事情，通常是具体问题具体分析；

除了掌握经典的动态规划问题以外，还需要多做题；

如果是针对面试，请自行把握难度。掌握常见问题的动态规划解法，理解动态规划解决问题，是从一个小规模问题出发，逐步得到大问题的解，并记录中间过程；

「动态规划」方法依然是「空间换时间」思想的体现，常见的解决问题的过程很像在「填表」。

此处liweiwei1419提及到的填表，是初学者理解动态规划运算过程非常好的一种方式，对于比较难的题目，不仅难在dp方程的定义，也难在初始化和动态规划整个过程多个循环嵌套时，遍历的方向，内外循环彼此位置的安排，有时将内循环变成外循环，很多问题就迎刃而解，有时将正序变成倒数，题目就会得到正确答案，

比如01背包和完全背包，01背包必须倒序进行，完全背包可以正序进行，

同样的，关于股票问题，在base case正确的情况下，将交易次数作为外循环，显然要简单很多，

这并不是一个玄学的过程，通过填表操作，就能很好的理解动态规划的运算过程，也能写出更高质量的代码。

3、初始化

初始化是非常重要的，一步错，步步错。初始化状态一定要设置对，才可能得到正确的结果。

角度 1：直接从状态的语义出发；

角度 2：如果状态的语义不好思考，就考虑「状态转移方程」的边界需要什么样初始化的条件；

角度 3：从「状态转移方程」方程的下标看是否需要多设置一行、一列表示「哨兵」（sentinel），这样可以避免一些特殊情况的讨论。

填表也是解决初始化问题的方法之一。

4、输出

有些时候是最后一个状态，有些时候可能会综合之前所有计算过的状态。

动态规划的题目之所以难，是因为题目本身非常考验做题者的抽象思维能力，如何把抽象问题具象化。

以上内容参考liweiwei1419所述，进行了部分的修改和简化

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-

以下内容分类参考leetcode上DP题目分类总结：

https://leetcode-cn.com/circle/article/NfHhXD/

https://leetcode-cn.com/circle/article/2Xxlw3/

1. 数塔

从斐波那契数列 到杨辉三角，其中的dp非常好设置，这些数列本身就很有规律性，按着规律就行进行操作，属于动态规划中比较简单和直观的题目

同样，我们会发现，题目要求我们让结果对1e9+7取模，原因大致如下：（来源：知乎@EntropyIncreaser）

面试题10- I. 斐波那契数列  https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

斐波那契数列的状态方程，初值就是其本身的计算公式，直接进行设置即可

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

class Solution {
public:int fib(int n) {if(n == 0) return 0;if(n == 1) return 1;int mod = 1e9+7;int F1 = 0,F2 = 1,Fres = 0;for(int i = 2;i<=n;++i){Fres = (F1 + F2)%mod;F1 = F2;F2 = Fres;}return Fres;}
};

类似问题：

1137. 第 N 个泰波那契数 https://leetcode-cn.com/problems/fibonacci-number/

118. 杨辉三角 https://leetcode-cn.com/problems/pascals-triangle/

119. 杨辉三角 II https://leetcode-cn.com/problems/pascals-triangle-ii/

杨辉三角和斐波那契数列如出一辙，初值也好，状态方程也好，都是题目给定好的，直接计算即可：

class Solution {
public:vector<int> getRow(int rowIndex) {vector<int> dp(rowIndex+1,1);//行数和列数关系for(int i = 2;i<=rowIndex;++i)//行数遍历{for(int j = 2;j<=i;++j){dp[j-1] = dp[j-1] + dp[j-2];}}return dp;  }
};

（错误版本） 

class Solution {
public:vector<int> getRow(int rowIndex) {vector<int> dp(rowIndex+1,1);//行数和列数关系for(int i = 2;i<=rowIndex;++i)//行数遍历{for(int j = i;j>1;--j){dp[j-1] = dp[j-1] + dp[j-2];}}return dp;  }
};

杨辉三角有个很有意思的地方，就是我们需要倒序（可进行内外循环关系） 

二维动态规划的状态方程很好给出

二维的动态规划随意循环，都是没有问题的，但是如果压缩到一维，内循环必须是倒序，从上面的程序输出结果我们也可以看出，从前往后正序计算，i= 3时，计算dp[2]的时候，dp[2] = dp[2]（此时为1） + dp[1]（此时为3，不是2，因为正序计算的时候将dp[1]更新了）；

这就是在不同状态方程下，我们需要注意的地方，有时候要采用不一样的循环策略

279. 完全平方数 https://leetcode-cn.com/problems/perfect-squares/

此题不如说是一道数学题，题目怎么要求咱们怎么设，状态方程如下：

下面我们需要给平方数一个取值上限，当然直接给n也可以，但是我们知道，一个数值一般都不会大于自身一般的平方

当a大于4的时候确实是如此，那么我们就让a/2为平方数的上限，下面的解法是直接开方，当然效果都是一样的，直接开方的循环次数会更小。

class Solution {
public:int numSquares(int n) {if(n == 0) return 0;vector<int> dp(n+1,n);dp[0] = 0;//dp[i]表示组成i，需要最少个数的完全平方数for(int i = 1;i<=n;++i){for(int j = 1;j*j<=i&&j<=sqrt(n);++j){dp[i] = min(dp[i],dp[i-j*j]+1);}}return dp[n];}
};

2. 背包

Leetcode动态规划——01背包问题：https://blog.csdn.net/qq_41605114/article/details/106059876

Leetcode动态规划—完全背包问题：https://blog.csdn.net/qq_41605114/article/details/106086262

3.路径

往后的几道路径问题，题目要求都很相似，都是在棋盘格上，要求从某点出发，最终到达某点，求路径总数，最短路径等等

路径问题的状态设置都非常类似，解题思路也大同小异，下面我们来总结一下：

（1）状态定义：一般都是二维dp，一般定义都是dp[i][j]:从起点到坐标为i,j的点，路径总数/最小路径和/出界概率/.....为dp[i][j]

（2）状态方程：从哪儿来？触发什么内容？

从哪儿来？有些题目（62/63）是从目标点[i][j]点的上面和左侧，有些题目则复杂一些（688/935），是以目标点[i][j]点为中心的八个

位置出发，都可以到目标点[i][j]，但是这些都不重要，状态方程就和这些能够到达目标点[i][j]的位置有关，有时候是全部加和，有时

候是比大小，这就要看题意了。

（3）初始值

设置按照逻辑和dp table来就好，路径问题的初值都很直观，很好设置主要分为以下部分：

边界处：需要根据题意进行设置，一般都非常明显

边界外：一般都是0，或者无效状态

边界内部：根据题意，有时需要将全部设置为1或者其他内容，路径问题的初值终点还是在边界外和边界处

（4）走N步/移动N次

参考688,935,576等题目，旗子的步长一定要作为外循环，为了保证dp table的前一个状态处于完整状态，不至于漏算少算一些情况！

62. 不同路径 https://leetcode-cn.com/problems/unique-paths/

求路径总数

class Solution {
public:int uniquePaths(int m, int n) {if(m < 0||n < 0) return 0;vector<vector<int>> dp(m+1,vector<int>(n+1,0));//设置dp[i][j]为，从起点出发，到该点的路径数量for(int i = 0;i<=m;++i) dp[i][1] = 1;for(int j = 0;j<=n;++j) dp[1][j] = 1;for(int i = 2;i<=m;++i){for(int j = 2;j<=n;++j){dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m][n];}
};

精选答案：https://leetcode-cn.com/problems/unique-paths/solution/kan-liao-jue-dui-dong-de-dong-tai-gui-hua-by-stree/

从哪儿来？ 

本题要求，只能从往下和往右，那么任意一个具有普世意义的点，要得到该点的路径和，那么只需要知道到达该点上面一个点和左侧一个点的路径和即可。

正如状态方程所示。

63. 不同路径 II https://leetcode-cn.com/problems/unique-paths-ii/

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size(),n = obstacleGrid[0].size();if(m == 0||n == 0) return 0;vector<vector<int>>dp(m+1,vector<int>(n+1,0));//全部初始化为0for(int i = 1;i<=m;++i){for(int j = 1;j<=n;++j){if(obstacleGrid[i-1][j-1] == 1) continue;if(j-2>=0&&obstacleGrid[i-1][j-2] == 1)//左边是障碍{if(i == 1) dp[i][j] = 0;else dp[i][j] = dp[i-1][j];continue;}else if(i-2>=0&&obstacleGrid[i-2][j-1] == 1)//上面是障碍{if(j == 1) dp[i][j] = 0;elsedp[i][j] = dp[i][j-1];continue;}if(i==1&&j==1) dp[i][j] = 1;else dp[i][j] = dp[i-1][j]+dp[i][j-1];}}return dp[m][n];}
};

官方解答：https://leetcode-cn.com/problems/unique-paths-ii/solution/bu-tong-lu-jing-ii-by-leetcode/

此题加入了障碍物，那么整个dp的定义思路和状态方程的定义思路还是不变，只是在细节部分作出修改

64. 最小路径和 https://leetcode-cn.com/problems/minimum-path-sum/

题目特别指出，从左上角到右下角，告诉了起点和终点，此题和62题没有什么不一样。

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size(),n = grid[0].size();if(m == 0||n == 0) return 0;//本题规定了起点和终点，起点是左上角，终点是右下角vector<vector<int>>dp(m+1,vector<int>(n+1,0));//dp表示以[1][1]为起点，以ij为结尾，最小路径和// dp[1][1] = grid[0][0];for(int i = 1;i<=m;++i){for(int j = 1;j<=n;++j){if(i == 1)//第一行{dp[i][j] = dp[i][j-1]+grid[i-1][j-1];continue;}if(j == 1)//第一列{dp[i][j] = dp[i-1][j]+grid[i-1][j-1];continue;}dp[i][j] = min(dp[i][j-1],dp[i-1][j])+grid[i-1][j-1];}}return dp[m][n];}
};

参考代码：

https://leetcode-cn.com/problems/minimum-path-sum/solution/zui-xiao-lu-jing-he-by-leetcode/

https://leetcode-cn.com/problems/minimum-path-sum/solution/zui-xiao-lu-jing-he-dong-tai-gui-hua-gui-fan-liu-c/

如果我们对上面的题目增加难度，不去规定起点和终点，那么我们应该怎么做？

931. 下降路径最小和 https://leetcode-cn.com/problems/minimum-falling-path-sum/

此题一看，和64题非常相似，但是还是有本质上的差别的，64题规定了起点和终点，931并没有在严格意义上要求起点和终点。

本题有一个问题，路径很多，dp最好的定义方式如下：

从哪儿来？ 

要到达指定点，出去边界，从三个方向，j，j+1，j-1。加上题目要求最小值，那么直接对比三者之中谁最小即可。

最后再次对比到达最后一行的最小路径中谁最小，完成输出

这种情况，在后面买票问题中也会出现，正序倒序都能解决问题。

class Solution {
public:int minFallingPathSum(vector<vector<int>>& A) {int depth = A.size(),size = A[0].size();if(depth == 0||size == 0) return 0;vector<vector<int>> dp(depth+1,vector<int>(size+1,0));dp[1][1] = A[0][0];for(int i = 1;i<=depth;++i){for(int j = 1;j<=size;++j){if(j == 1&&j == size){dp[i][j] = dp[i-1][j]+A[i-1][j-1];continue;}if(j == 1){dp[i][j] = min(dp[i-1][j],dp[i-1][j+1])+A[i-1][j-1];continue;}if(j == size){dp[i][j] = min(dp[i-1][j-1],dp[i-1][j])+A[i-1][j-1];;continue;}dp[i][j] = min(dp[i-1][j],min(dp[i-1][j-1],dp[i-1][j+1]))+A[i-1][j-1];}}int MIN = INT_MAX;for(int j = 1;j<=size;++j){MIN = min(MIN,dp[depth][j]);}return MIN;}
};

120. 三角形最小路径和 https://leetcode-cn.com/problems/triangle/

如果对931有了深刻的认识，那么120这道题也就没有什么难度了。

状态及状态方程的定义，都是如出一辙，只是边界条件稍有区别而已。

class Solution {
public:int minimumTotal(vector<vector<int>>& triangle) {int depth = triangle.size(),size = triangle[depth-1].size();if(size == 0||depth == 0) return 0;vector<vector<int>> dp(depth+1,vector<int>(size+1,0));//第i层第j个元素为路径结尾时的最小路径和，dp设置好，事半功倍dp[1][1] = triangle[0][0];//从第一层第一个元素for(int i = 2;i<=depth;++i){for(int j = 1;j<=triangle[i-1].size();++j){if(j == 1)//第一个元素特殊，上面没有第0个,上一层来源只能是同序号的{dp[i][j] = dp[i-1][j]+triangle[i-1][j-1];continue;}else if(j == triangle[i-1].size())//最后一个元素特殊,上一层来源只能是同序号-1的{dp[i][j] = dp[i-1][j-1]+triangle[i-1][j-1];continue;}dp[i][j] = min(dp[i-1][j],dp[i-1][j-1])+triangle[i-1][j-1];}}int MIN = INT_MAX;for(int j = 1;j<=size;++j){MIN = min(MIN,dp[depth][j]);}return MIN;}
};

主要参考：

https://leetcode-cn.com/problems/triangle/solution/javadong-tai-gui-hua-si-lu-yi-ji-dai-ma-shi-xian-b/ 

935. 骑士拨号器 https://leetcode-cn.com/problems/knight-dialer/

此题可以说是检验上面几道题目的综合版本，虽然不再是简单的从上或者从右到达指定点，但是本质上是一样的。

本题增加了步数限制，所以需要对dp进行进一步约束，增加步数限制

和其他路径题目一样，只不过增加了步数限制

dp定义如下：

vector<vector<vector<unsigned int>>> dp(4+4,vector<vector<unsigned int>>(3+4,vector<unsigned int>(N+1,0)));
//dp表示ij为起点，摁下了N个数字，方案有多少种,根据题意

至于范围为什么如此设置也是有原因的，和状态方程的设置很有关系。

将拨号键范围内的内容，初始化为1，也就是图中蓝色底纹部分。

如果只摁下一个摁键，那么，那么到达每个数字对应的位置的方案就各为1，最终将所有拨号键范围内数字步数加和即可。

最外侧循环是摁下的数字个数，摁下一个摁键的情况已经包含在初始化中，所有从摁下两次开始。

下面分析一些dp状态方程的推导过程，

如果想到到达数字1，可以从图中绿色标记的各个点出发，那么状态方程就很好理解，要第N次到达（摁下）的数字是a，那么第N-1次到达（摁下）的数字只肯是是图中绿色标记的位置，方案总数或者路径总数就是这些可能性的总和。 

class Solution {
public:int knightDialer(int N) {if(N == 0) return 0;int mod = 1e9+7;vector<vector<vector<unsigned int>>> dp(4+4,vector<vector<unsigned int>>(3+4,vector<unsigned int>(N+1,0)));//dp表示ij为起点，摁下了N个数字，方案有多少种,根据题意for(int i = 0;i<8;++i){for(int j = 0;j<7;++j){if((i>=2&&i<=4)&&(j>=2&&j<=4))dp[i][j][1] = 1;}}dp[5][3][1]=1;for(int n = 2;n<=N;++n){for(int i = 2;i<=5;++i){for(int j = 2;j<=4;++j){if(i == 5&&(j==2||j==4)){dp[i][j][n] = 0;continue;}dp[i][j][n] = (dp[i-1][j-2][n-1]+dp[i-2][j-1][n-1]+dp[i-2][j+1][n-1]+dp[i-1][j+2][n-1]+dp[i+1][j-2][n-1]+dp[i+2][j-1][n-1]+dp[i+2][j+1][n-1]+dp[i+1][j+2][n-1])%mod;}}}//把起点遍历一遍int sum = 0;for(int i = 2;i<=4;++i){for(int j = 2;j<=4;++j){sum = (sum+dp[i][j][N])%mod;}}sum = (sum+dp[5][3][N])%mod;return sum;}
};

下面是同类型的一道题目 

688. “马”在棋盘上的概率 https://leetcode-cn.com/problems/knight-probability-in-chessboard/

国际象棋类型的题目，dp[i][j][k]可以理解为从i，j出发，走k步还在棋盘格上的概率。

也可以理解成走了k步，到达i，j的概率。

class Solution {
public:double knightProbability(int N, int K, int r, int c) {vector<vector<vector<double>>>dp(N+4,vector<vector<double>>(N+4,vector<double>(K+1,0)));//dp[i][j][k]:表示，从ij开始，走k步还在棋盘内的概率//那么开始初始化，ij属于[2,N+1]范围内的概率，k == 0时，全部是1，因为在棋盘内走0步，还在棋盘内的概率为1，其余的部分，概率均为0。因为本身就在棋盘外，移动k==0步，还是在棋盘外for(int j = 0;j<N+4;++j){for(int i = 0;i<N+4;++i){if((j>=2&&j<=N+1)&&(i>=2&&i<=N+1))dp[i][j][0] = 1;}}for(int k = 1;k<=K;++k){for(int i = 2;i<=N+1;++i){for(int j = 2;j<=N+1;++j){dp[i][j][k] = (dp[i-1][j-2][k-1]+dp[i-2][j-1][k-1]+dp[i-2][j+1][k-1]+dp[i-1][j+2][k-1]+dp[i+1][j-2][k-1]+dp[i+2][j-1][k-1]+dp[i+2][j+1][k-1]+dp[i+1][j+2][k-1])/8.0;}}}return dp[r+2][c+2][K];}
};

以上两道题目特别注意，旗子的步长一定要作为外循环，为了保证dp table的前一个状态处于完整状态，不至于漏算少算一些情况！ 

主要参考 

https://leetcode-cn.com/problems/knight-probability-in-chessboard/solution/ma-zai-qi-pan-shang-de-gai-lu-by-leetcode/

https://leetcode-cn.com/problems/knight-probability-in-chessboard/solution/zhuang-tai-ji-de-zai-ci-ying-yong-by-christmas_wan/

576. 出界的路径数 https://leetcode-cn.com/problems/out-of-boundary-paths/

https://leetcode-cn.com/problems/out-of-boundary-paths/solution/zhuang-tai-ji-du-shi-zhuang-tai-ji-by-christmas_wa/

此题也是一样的，能计算留着界内路径数，也就能计算走出界限路径数，从哪儿来，上下左右都能来，那么就定义dp为该点上下左右出界路径的总和，base case就是将外界一圈，步数为0的区域，不用走就在界外的这些情况设置为零。

class Solution {
public:int findPaths(int m, int n, int N, int begin, int end) {int mod = 1e9+7;vector<vector<vector<unsigned long long>>>dp(m+2,vector<vector<unsigned long long>>(n+2,vector<unsigned long long>(N+1,0)));//初始化base case将范围内的，也就是mxn四周的值全部初始化为1//dp[i][j][k]从ij出发，走k步走到外界for(int j = 0;j<n+2;++j){dp[0][j][0] = 1;//第一行dp[m+1][j][0] = 1;//最后一行}for(int i = 0;i<m+2;++i){dp[i][0][0] = 1;//第一列dp[i][n+1][0] = 1;//最后一列}for(int k = 1;k<=N;++k)//步长需要放在外侧循环，因为要考虑到所有组合可能性，也是为了让表的其他部分填写完整{for(int i = 1;i<=m;++i){for(int j = 1;j<=n;++j){dp[i][j][k] = (dp[i-1][j][k-1]+dp[i+1][j][k-1]+dp[i][j-1][k-1]+dp[i][j+1][k-1])%mod;}}}int sum = 0;for(int k = 1;k<=N;++k)sum = (sum+dp[begin+1][end+1][k])%mod;return sum;}
};

1220. 统计元音字母序列的数目 https://leetcode-cn.com/problems/count-vowels-permutation/

class Solution {
public:int countVowelPermutation(int n) {int mod = 1e9+7;vector<vector<unsigned long long int>>dp(n+1,vector<unsigned long long int>(6,0));//dp含义：字符串长度为n，以i结尾的字符串，有几种组合方式for(int i= 1;i<=5;++i)dp[1][i] = 1;for(int size = 2;size<=n;++size){for(int i = 1;i<=5;++i){if(i == 1)//adp[size][i] = (dp[size-1][2] + dp[size-1][5] + dp[size-1][3])%mod ;//前面可以是2e和5u和3ielse if(i == 2)//edp[size][i] = (dp[size-1][1]  + dp[size-1][3])%mod;//前面可以是1a和3ielse if(i == 3)//idp[size][i] = (dp[size-1][2] + dp[size-1][4])%mod;//前面可以是2e和4oelse if(i == 5)//udp[size][i] = (dp[size-1][4] + dp[size-1][3])%mod;//前面可以是4oelse //0dp[size][i] = dp[size-1][3];//前面可以是3i}}int sum = 0;for(int i = 1;i<=5;++i){sum = (sum + dp[n][i])%mod;}return sum;}
};

https://leetcode-cn.com/problems/count-vowels-permutation/solution/dang-wo-men-zai-tan-dong-tai-gui-hua-de-shi-hou-wo/

4骰子

1223. 掷骰子模拟 https://leetcode-cn.com/problems/dice-roll-simulation/

class Solution {
public:int dieSimulator(int n, vector<int>& rollMax) {int size = rollMax.size();if(size == 0) return 0;int MAX = 0,mod = 1e9+7;for(auto item:rollMax) MAX = max(MAX,item);vector<vector<vector<int>>>dp(n+1,vector<vector<int>>(7,vector<int>(MAX+1,0)));//dp[i][j][k],投掷了i次，本次点数为j（以j结尾），本次点数出现了k次，如此情况下的组合数//base casefor(int j = 1;j<=6;++j){dp[1][j][1] = 1;//投掷一次，该数字出现一次，组合数自然是1}for(int i = 2;i<=n;++i)//投掷次数{for(int j = 1;j<=6;++j)//本次投掷出现的点数{for(int k = 1;k<=6;++k)//上次出现的点数{if(j == k)//本次点数和上次一样{for(int t = 1;t<rollMax[k-1];++t)//此时，是k是j无所谓//循环出现次数，因为大前提是连续出现，所以不能等于rollMax[j]dp[i][j][t+1] = (dp[i][j][t+1] + dp[i-1][k][t])%mod;}else{for(int t = 1;t<=rollMax[k-1];++t)//此时，必须是k，因为此时循环的目的是上一个点连续出现不同次数的全部清空//循环出现次数，因为上次出现的点数和本次点数不一样dp[i][j][1] = (dp[i][j][1] + dp[i-1][k][t])%mod;//相当于连续第一次出现}}}}int sum = 0;for(int j = 1;j<=6;++j)//不同的点数{for(int t = 1;t<=rollMax[j-1];++t)//以不同点数结尾，连续出现的次数sum = (sum + dp[n][j][t])%mod;}return sum;}
};

本题最难的连续这个状态，以某元素结尾，可以选择从1到连续上限的各种方式进行排列，不考虑这一点的话，会少算很多情况。（意识到这点，本题就解决了一半）

 第一个循环：投掷次数

第二个循环：出现的点数，第三个上一次出现的点数，

如果本次和上一次一样，那么本次就是t+1次结尾，等于以本次点数结尾的所有情况之和（以上次点数连续n次结尾的情况，n在规定范围内）

如果本次和上一次不一样，以本次点数结尾的情况，就等于以上次点数结尾的所有情况（以上次点数连续n次结尾的情况，n在规定范围内）

第三个参数，连续出现的次数，也是非常关键的细节，如果上次出现和数字和本子投掷的一样，那么就是连续出现2次；

如果不一样，那么就是连续出现1次，这个对状态方程是有影响的，第一种情况本次和上次一样，那么因为不知道上上次的情况，此时就要穷尽所有的可能性：

                    if(j == k)//本次点数和上次一样{for(int t = 1;t<rollMax[k-1];++t)//此时，是k是j无所谓//循环出现次数，因为大前提是连续出现，所以不能等于rollMax[j]dp[i][j][t+1] = (dp[i][j][t+1] + dp[i-1][k][t])%mod;}

反之，如果不一样，那么就当连续出现1次处理：

                        for(int t = 1;t<=rollMax[k-1];++t)//此时，必须是k，因为此时循环的目的是上一个点连续出现不同次数的全部清空//循环出现次数，因为上次出现的点数和本次点数不一样dp[i][j][1] = (dp[i][j][1] + dp[i-1][k][t])%mod;//相当于连续第一次出现}

本题思路参考：https://leetcode-cn.com/problems/dice-roll-simulation/solution/jin-liang-jian-dan-di-ba-si-lu-jiang-ming-bai-by-m/

1155. 掷骰子的N种方法 

https://leetcode-cn.com/problems/number-of-dice-rolls-with-target-sum/

最初的想法：

class Solution {
public:int numRollsToTarget(int d, int f, int target) {if(target == 0||(d*f)< target) return 0;int mod = 1e9+7;vector<vector<int>> dp(d+1,vector<int>(target+1,0));//dp[i][j] = i个骰子，凑成target的情况数(一个骰子只能投一次)for(int k = 1;k<=f&&k<=target;++k)//base case初始化{dp[1][k] = 1;}for(int i = 2;i<=d;++i)//骰子个数{for(int j = 1;j<=target;++j)//能凑成的金额{for(int k = 1;k<=f;++k)//骰子面额if(j-k>=0)dp[i][j] = (dp[i][j]+dp[i-1][j-k])%mod;}}return dp[d][target];}
};

也很好理解，第i个骰子的情况，要从第i-1个骰子的情况导出，第i个骰子点数为k，那么第i-1个骰子的点数为j-k即可完成目标。

5约束

746. 使用最小花费爬楼梯

https://leetcode-cn.com/problems/min-cost-climbing-stairs/

参考内容： 

https://leetcode-cn.com/problems/min-cost-climbing-stairs/solution/yi-bu-yi-bu-tui-dao-dong-tai-gui-hua-de-duo-chong-/

还是分两种情况，是否要踩上目前的所在的台阶

踩上：dp[i-1] + cost[i]

不踩上：dp[i-2] + cost[i-1]

此题务必注意初值的选择，题意也稍不好理解，写代码的时候也要注意。

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int size = cost.size();vector<int> dp(size,0);dp[0] = 0;dp[1] = min(cost[0], cost[1]);//第一个台阶是可以选择的，选择最小的即可for (int i = 2; i < size; i++) {dp[i] = min(dp[i - 1] + cost[i], dp[i - 2] + cost[i - 1]);}return dp[size - 1];}
};

198. 打家劫舍

https://leetcode-cn.com/problems/house-robber/

可以参考下文，给出了整个过程的动态流程

https://leetcode-cn.com/problems/house-robber/solution/hua-jie-suan-fa-198-da-jia-jie-she-by-guanpengchn/

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

213. 打家劫舍 II https://leetcode-cn.com/problems/house-robber-ii/

最初未优化版本：有待优化

class Solution {
public:int rob(vector<int>& nums) {int size = nums.size();if(size == 0) return 0;if(size == 1) return nums[0];vector<int> dp(size+1,0);int temp1 = begin(dp,nums[0],0,nums);cout<<temp1;int temp2 = begin(dp,nums[1],1,nums);cout<<temp2;return max(temp1,temp2);}int begin(vector<int> & dp,int beginval,int flag,vector<int> & nums){int size = nums.size();dp[1] = beginval;for(int i = 2;i<=size;++i){if(i == size&&flag == 0) dp[i] = dp[i-1];//如果选了第一个，最后一个不能选else if(i == 2&&flag == 1) {dp[i] = dp[i-1];dp[i-1] = 0;}//如果没有选第一个else dp[i] = max(dp[i-1],dp[i-2]+nums[i-1]);}return dp[size];}
};

337. 打家劫舍 III https://leetcode-cn.com/problems/house-robber-iii/

最初没有优化的方法：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int rob(TreeNode* root) {if(root == nullptr)return 0;queue<TreeNode*> q;q.push(root);vector<int> V;while(!q.empty()){int qsize = q.size();int Valtemp = 0;for(int i = 0;i<qsize;++i){TreeNode* temp = q.front();q.pop();if(temp->left) q.push(temp->left);if(temp->right) q.push(temp->right);Valtemp += temp->val;}V.push_back(Valtemp);}int Path1 = 0,Path2 = 0;for(int i = 0;i<V.size();i += 2) Path1 += V[i];for(int j = 1;j<V.size();j += 2) Path2 += V[j];if(Path1<Path2) return Path2;else return Path1;}
};

6股票问题

本文关于股票问题，主要参考一下内容

股票问题模板如下：

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])max(   选择 rest  ,           选择 sell      )解释：今天我没有持有股票，有两种可能：
要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])max(   选择 rest  ,           选择 buy         )解释：今天我持有着股票，有两种可能：
要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。作者：labuladong
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

@liweiwei1419对股票问题进行了极其详尽的分析

@labuladong对股票问题进行了整理，给出了一套完整的模板（链接如下：） 

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/

其中也对初值提出了要求：

dp[-1][k][0] = 0
解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。
dp[-1][k][1] = -infinity
解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。dp[i][0][0] = 0
解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。
dp[i][0][1] = -infinity
解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。作者：labuladong
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

base case：
dp[-1][k][0] = dp[i][0][0] = 0
dp[-1][k][1] = dp[i][0][1] = -infinity状态转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])作者：labuladong
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 下面我们来看题目： 

121. 买卖股票的最佳时机 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

只能交易一次 

class Solution {
public:int maxProfit(vector<int>& prices) {int size = prices.size();if(size < 2) return 0;vector<vector<int>> dp(size+1,vector<int>(2,0));//dp表示在第i天，持有或未持有的状态下，所得到的最大利润// for(int i = 1;i<=size;++i) dp[i][] = ;dp[0][1] = -prices[0];dp[0][0] = 0;for(int i = 1;i<=size;++i){dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i-1]);//今天未持有，表示今天卖了，或者昨天就没有持有dp[i][1] = max(dp[i-1][1],0-prices[i-1]);//今天持有，表示今天买了了，或者昨天就持有}return dp[size][0];//最大利润，就是在规定天数内完成交易，而不是留着手里}
};

本题有两种状态：天数，持有还是未持有，dp状态方程一定是要将所有的状态覆盖的，不然不能称之为状态方程

尽可能多的交易

122. 买卖股票的最佳时机 II https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

class Solution {
public:int maxProfit(vector<int>& prices) {int size = prices.size();if(size < 2) return 0;vector<vector<int>> dp(size+1,vector<int>(2,0));//dp表示在第i天，持有或未持有的状态下，所得到的最大利润dp[0][1] = -prices[0];//第0天持有股票，不可能，因为后面求最值，所以负无穷dp[0][0] = 0;//没有持有股票，利润为零for(int i = 1;i<=size;++i){dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i-1]);//今天未持有，1表示今天卖了，2昨天就没有持有dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i-1]);//本题允许完成无数次交易，买入必须在卖出之前，dp[i-1][0]-prices[i-1]表示今天买了//今天持有，2表示今天买了了，1昨天就持有}return dp[size][0];//最大利润，就是在规定天数内完成交易，而不是留着手里}
};

从初始状态方程定base case

增加约束

309. 最佳买卖股票时机含冷冻期 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

冷冻期

class Solution {
public:int maxProfit(vector<int>& prices) {int size = prices.size();if(size < 2) return 0;vector<vector<int>> dp(size+1,vector<int>(2,0));//dp表示在第i天，持有或未持有的状态下，所得到的最大利润dp[0][1] = -prices[0];//第0天持有股票，不可能，因为后面求最值，所以负无穷dp[0][0] = 0;//没有持有股票，利润为零dp[1][1] = -prices[0];//第1天持有股票，只能买了dp[1][0] = 0;//没有持有股票，利润为零for(int i = 2;i<=size;++i){dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i-1]);//今天未持有，1表示今天卖了，2昨天就没有持有dp[i][1] = max(dp[i-1][1],dp[i-2][0]-prices[i-1]);//本题允许完成无数次交易，买入必须在卖出之前，加上要考虑冷冻期，dp[i-2][0]-prices[i-1]表示今天买了//今天持有，2表示今天买了了，1昨天就持有}return dp[size][0];//最大利润，就是在规定天数内完成交易，而不是留着手里}
};

手续费

714. 买卖股票的最佳时机含手续费 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int size = prices.size();if(size < 2) return 0;vector<vector<int>> dp(size+1,vector<int>(2,0));//dp表示在第i天，持有或未持有的状态下，所得到的最大利润dp[0][1] = -prices[0];//第0天持有股票，不可能，因为后面求最值，所以负无穷dp[0][0] = 0;//没有持有股票，利润为零for(int i = 1;i<=size;++i){dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i-1]-fee);//今天未持有，1表示今天卖了，2昨天就没有持有dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i-1]);//本题允许完成无数次交易，买入必须在卖出之前，dp[i-1][0]-prices[i-1]表示今天买了//今天持有，2表示今天买了了，1昨天就持有}return dp[size][0];//最大利润，就是在规定天数内完成交易，而不是留着手里}
};

限制交易次数

下面会列出dp table，我们从中就可以看出，外循环是天数还是交易次数，都无关紧要。

从状态方程中我们也能看出，先按k = 1计算一行，还是先按照i=1计算一列，问题都不会受到影响

绿色部分对应的dp状态方程如下：

dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1]+prices[i-1]);

灰色部分对应的dp状态方程如下：

dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i-1]);

123. 买卖股票的最佳时机 III https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

base case 的情况还是一样的，第0天，未持有利润为0，持有为无效状态

class Solution {
public:int maxProfit(vector<int>& prices) {int size = prices.size(),K = 2;if(size < 2) return 0;vector<vector<vector<int>>>dp(size+1,vector<vector<int>>(K+1,vector<int>(2,0)));//表示在第i天，完成k次交易，目前手中是否持有股票的情况下，最大利润for(int k = 1;k<=K;++k){dp[0][k][1] = -prices[0];//第0天持有股票，不可能，因为后面求最值，所以负无穷dp[0][k][0] = 0;//没有持有股票，利润为零}for(int i = 1;i<=size;++i)//天数{for(int k = 1;k<=K;++k)//交易次数{dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1]+prices[i-1]);// cout<<"i:"<<i<<"0:"<<dp[i][k][0]<<endl;//未持有，昨天就未持有，今天才卖的dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i-1]);// cout<<"i:"<<i<<"1:"<<dp[i][k][1]<<endl;//持有，昨天就持有，今天才买的}}return dp[size][K][0];}
};

其中内外循环可以颠倒：

        for(int k = 1;k<=K;++k)//交易次数{for(int i = 1;i<=size;++i)//天数{dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1]+prices[i-1]);// cout<<"i:"<<i<<"0:"<<dp[i][k][0]<<endl;//未持有，昨天就未持有，今天才卖的dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i-1]);// cout<<"i:"<<i<<"1:"<<dp[i][k][1]<<endl;//持有，昨天就持有，今天才买的}}

188. 买卖股票的最佳时机 IV https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/ 

此处的初值最后是对天数为0的状态开始设置，比较好理解，要去初始化天数为1的情况，不好理解，如果要初始化天数为1，循环从第二天开始，初始化部分如下：

        dp[1][2][0] = -prices[0];//不可能状态dp[1][2][1] = -prices[0];//不可能状态dp[1][1][0] = 0;//交易一次但是没有持有dp[1][1][1] = -prices[0];//不可能状态dp[1][0][0] = 0;//不交易不持有，固然是0dp[1][0][1] = -prices[0];//不可能状态

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int size = prices.size();if(size < 2) return 0;if(k >= prices.size()/2)//加一个保险措施，交易次数大于可交易天数的一半{int sum = 0;for(int i = 1; i < prices.size(); i++){int val = prices[i] - prices[i - 1];sum += (val > 0? val: 0);}return sum;}vector<vector<vector<int>>>dp(size+1,vector<vector<int>>(k+1,vector<int>(2,0)));//表示在第i天，完成k次交易，目前手中是否持有股票的情况下，所取得的最大利润for(int j = 1;j<=k;++j){dp[0][j][1] = -prices[0];//第0天持有股票，不可能，因为后面求的是最大值，所以负无穷dp[0][j][0] = 0;//没有持有股票，利润为零}for(int j = 1;j<=k;++j)//交易次数{for(int i = 1;i<=size;++i)//天数{dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j][1]+prices[i-1]);//未持有，昨天就未持有，今天才卖的cout<<"i  :"<<i<<"   "<<dp[i][k][0]<<endl;dp[i][j][1] = max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i-1]);//持有，昨天就持有，今天才买的cout<<"i  :"<<i<<"   "<<dp[i][k][1]<<endl;}}return dp[size][k][0];}
};

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/zhuang-tai-ya-suo-shi-guan-yu-kshi-fou-dao-xu-yao-/

那么k=2也可以这么写

class Solution {
public:int maxProfit(vector<int>& prices) {int size = prices.size(),K = 2;if(size < 2) return 0;vector<vector<vector<int>>>dp(size+1,vector<vector<int>>(K+1,vector<int>(2,0)));//表示在第i天，完成k次交易，目前手中是否持有股票的情况下，所取得的最大利润for(int k = 1;k<=K;++k){dp[0][k][1] = -prices[0];//第0天持有股票，不可能，因为后面求的是最大值，所以负无穷dp[0][k][0] = 0;//没有持有股票，利润为零}for(int k = 1;k<=K;++k)//交易次数{for(int i = 1;i<=size;++i)//天数{dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1]+prices[i-1]);//未持有，昨天就未持有，今天才卖的cout<<"i  :"<<i<<"   "<<dp[i][k][0]<<endl;dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i-1]);//持有，昨天就持有，今天才买的cout<<"i  :"<<i<<"   "<<dp[i][k][1]<<endl;}}return dp[size][K][0];}
};

让交易次数为外循环

6区间 DP

都是鬼才解法，不看答案鬼才能知道怎么解

1277. 统计全为 1 的正方形子矩阵

https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones/

参考内容：

https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones/solution/tong-ji-quan-wei-1-de-zheng-fang-xing-zi-ju-zhen-2/

（来源：leetcode官方） 

相当巧妙的方式方法，而此解法，也成为了区间DP题目和核心状态方程

第一行第一列的值就是上面表达式的第一行，如果矩阵的值是0，那么也没的算了

class Solution {
public:int countSquares(vector<vector<int>>& matrix) {int m = matrix.size(),n = matrix[0].size();vector<vector<int>>dp(m+1,vector<int>(n+1,0));//dp[i][j]以ij为右下角的正方形，个数int sum = 0;for(int i = 1;i<=m;++i){for(int j = 1;j<=n;++j){if(i == 1||j == 1)//第一行第一列dp[i][j] = matrix[i-1][j-1];else if(matrix[i-1][j-1] ==0)dp[i][j] = 0;else dp[i][j] = min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]))+1;sum += dp[i][j];}}return sum;}
};

 221. 最大正方形

https://leetcode-cn.com/problems/maximal-square/

参考内容：

https://leetcode-cn.com/problems/maximal-square/solution/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/

class Solution {
public:int maximalSquare(vector<vector<char>>& matrix) {if(matrix.empty()||matrix[0].empty()) return 0;int m = matrix.size(),n = matrix[0].size();int L = 0;vector<vector<int>> dp(m+1,vector<int>(n+1,0));for(int i = 1;i<=m;++i){for(int j = 1;j<=n;++j){if(matrix[i-1][j-1] == '1'){if(i==1||j==1)dp[i][j] = 1;else dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;}L = max(L,dp[i][j]);}}return L*L;}
};

以上两个题非常的相似，其实dp定义好了就很好计算这种题目，dp都是以ij为右下角的正方形最大的边长

注意，核心是以ij为正方形的右下角，这是非常关键的一个点，可以说是结题的核心了

96. 不同的二叉搜索树

https://leetcode-cn.com/problems/minimum-score-triangulation-of-polygon/

参考内容：

https://leetcode-cn.com/problems/unique-binary-search-trees/solution/bu-tong-de-er-cha-sou-suo-shu-by-leetcode/

https://leetcode-cn.com/problems/unique-binary-search-trees/solution/96bu-tong-de-er-cha-sou-suo-shu-cduo-chong-jie-fa-/

本题技巧性极强。

class Solution {
public:int numTrees(int n) {if(n == 0) return 0;vector<int> dp(n+1,0);//长度为n的序列的不同二叉搜索树个数(和序列内容无关，之和长度有关)dp[0] = 1;dp[1] = 1;for(int i = 2;i<=n;++i)//长度为i的序列{for(int j = 1;j<=i;++j)//长度为n的序列元素{dp[i] += dp[j-1]*dp[i-j];//j为根时，以j为根，将序列分为两个部分}}return dp[n];}
};

5419. 两个子序列的最大点积 https://leetcode-cn.com/problems/max-dot-product-of-two-subsequences/

来自于一道周赛的题目：

class Solution {
public:int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {int sz1=nums1.size(),sz2=nums2.size();vector<vector<int>> dp(sz1+1,vector<int>(sz2+1,-1e8));//初值是-1e8for(int i=1;i<=sz1;i++){for(int j=1;j<=sz2;j++){//1.1dp[i][j]=nums1[i-1]*nums2[j-1];//1.2dp[i][j]=max(dp[i][j],dp[i][j]+dp[i-1][j-1]);//2dp[i][j]=max(dp[i][j],dp[i][j-1]);//3dp[i][j]=max(dp[i][j],dp[i-1][j]);//4dp[i][j]=max(dp[i][j],dp[i-1][j-1]);}}return dp[sz1][sz2];}
};// 作者：smilyt_
// 链接：https://leetcode-cn.com/problems/max-dot-product-of-two-subsequences/solution/c-dong-tai-gui-hua-yi-dong-by-smilyt_/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我们可以这么定义dp：

dp[i][j]:第一个序列从1到i，第二个序列从1到j，选择元素相乘得到的最大点积

那么状态方程是什么呢？

1：只选择第i和第j个：dp[i][j] = nums[i]*nums[j]
2：选择第i和第j个：dp[i][j] = dp[i-1][j-1]+nums[i]*nums[j]
3：不选择第i和第j个：dp[i][j] = dp[i-1][j-1];
因为可以自由组合，那么有：
4：选择第i个，不选择第j个：dp[i][j] = dp[i][j-1];
5：不选择第i个，选择第j个：dp[i][j] = dp[i-1][j];

那么我们综合考虑以上四种情况，选择最值即可。

base case全部是-1e8，因为后面要比大小，需要设置为无效模式

7最长子序列/子字符串

300. 最长上升子序列

https://leetcode-cn.com/problems/longest-increasing-subsequence/

给定一个无序的整数数组，找到其中最长上升子序列的长度。

截图来源：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/

这题，暴力能不能算，那是当然，从第一个元素遍历，不断和后面的数值比较，大于，更新指针位置顺便更改能组成的长度。

        for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {if (cur < nums[j]) {cur = nums[j];length++;}}}

大致逻辑如上，遇到比cur目前指向的大，增加长度，更新cur指向。

那么我们在这个过程中，怎么标记我们找到的序列长度？是以某元素开头的最长序列为x，还是以某元素结尾的最长序列长度为x

这两种方式我们应该选择哪儿一种？选以某元素结尾的最长序列长度为x。循环的次数最少，以第一个元素开头，要循环n次，以第一个元素结尾，只需要循环1次。

那么整个过程中有没有重复的计算呢？暴力解法当然有，下面我们就利用

状态转移方程

dp表是为了解决重叠子问题

截图来源：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int size = nums.size();if(size == 0) return 0;vector<int> dp(size,1);//存放以某个元素结尾，能组成最长的序列的长度,默认长度就是1int MAX = 0;for(int i = 0;i<size;++i){for(int j = 0;j<i;++j)//j 的上限是 i,因为是以i结尾，只看i前面的数值{if(nums[j]<nums[i])//前面的数值一旦小于i本身，那么就可以加入i结尾的序列{dp[i] = max(dp[i],dp[j]+1);}}MAX = max(MAX,dp[i]);//最终要找最长的，那么找到dp的最大值即可。}return MAX;}
};

139. 单词拆分

https://leetcode-cn.com/problems/word-break/

dp[i]表示，第1到i个子字符串，能不能被拆分成字典中的元素。

给两个指针，i和j，i从1开始，终点为字符串长度，意义为每次给出原始字符串的子字符串，看看能不能被拆解为字典中的元素

j表示所给定子字符串的分割位置，将子字符串分割为s1（0，j-1）和s2（j，i-j）

以leetcode举例子，当j=4的时候，s1（0，j-1） = leet，s2（j，i-j） = code；

使用C++库函数substr（pos,n），返回一个string，包含s中从pos开始的n个字符的拷贝

我们两个循环，外循环控制整个字符串中子字符串的分割情况，内循环控制子字符串内部的分割情况

当s1在能被字典中的元素组成的时候，dp[j] == true

s2也能够被字典中的元素组成的时候，words.find(s.substr(j, i-j)) != words.end()

二者同时存在，说明长度为i的子字符串dp[i] == true。

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {set<string> words;for(int i=0; i<wordDict.size(); i++){words.insert(wordDict[i]);}vector<bool> dp(s.length()+1);dp[0] = true;for (int i = 1; i <= s.length(); i++) {for (int j = 0; j < i; j++) {if (dp[j] && words.find(s.substr(j, i-j)) != words.end() ) {dp[i] = true;break;}}}return dp[s.length()];}
};

8回文子序列/子字符串

回文子序列或子串

在动态规划中，回文有一个较为通用的模板：

dp[i][j]以ij做收尾的子串是回文的情况

子串和子序列是有区别的，子串必须是连续的，子序列可以是离散的 

5. 最长回文子串 

https://leetcode-cn.com/problems/longest-palindromic-substring/

 https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/（主要参考）

所以，我们设dp如下：

状态方程也很好列出：

本题还有个细节，就是dp table的情况，看下图

所以需要控制后限，如下程序所示，保证都算了

我们再来看看完整版本的dp table

如果我们要求1到6子串是不是回文，此时1和6相等，那么剩下的就完全取决于2到5了

所以首先要计算2到5，也就是控制终点，从1到size，起点在1到终点j之间即可。

从图上也很清晰的可以看出，我们应该怎么进行计算

class Solution {
public:string longestPalindrome(string s) {int size = s.size();if(size == 0) return "";int MAX = 0;string Res;vector<vector<bool>>dp(size+1,vector<bool>(size+1,false));for(int i = 1;i<=size;++i) dp[i][i] = true;//单个元素算回文for(int j = 1;j<=size;++j)//必须固定后限进行循环{for(int i = 1;i<=j;++i){if(s[i-1] == s[j-1]){// cout<<"123"<<endl;if(j-i+1<=3) dp[i][j] = true;else dp[i][j] = dp[i+1][j-1];}else dp[i][j] = false;if(dp[i][j]&&MAX<(j-i+1)){MAX = j-i+1;Res = s.substr(i-1,MAX);// cout<<"MAX  "<<MAX<<endl;}}}return Res;}
};

516. 最长回文子序列

https://leetcode-cn.com/problems/longest-palindromic-subsequence/ 

我们把子串改成子序列，难度升级。

就是状态方程有所改变，因为是求子序列的最长长度，求啥设啥，就让dp为长度

我们继续按照上一题的思路思考，此时是子序列，而之前是子串，子串是必须连续的，那么我们只考虑i+1和j-1的情况就可以了

但是子序列内容，需要考虑情况就自然要多

当i和j不相等的时候，我们要考虑整个组合的情况，三者比大小，最大的作为dp[i][j]的值。下面我们列出状态方程：

下面我们看看dp table，看看如何计算：

j要从底端晚上算，i要从小到大算，base case不用计算已经给好了

完整代码如下：

class Solution {
public:int longestPalindromeSubseq(string s) {int size = s.size();if(size == 0) return 0;vector<vector<int>> dp(size+1,vector<int>(size+1,0));//以i开始，j结束，字符串在此区间内最长的回文子序列for(int i = 1;i<=size;++i) dp[i][i] = 1;for(int j = 1;j<=size;++j){for(int i = j-1;i>=1;--i){if(s[i-1] == s[j-1]) dp[i][j] = dp[i+1][j-1]+2;elsedp[i][j] = max(dp[i+1][j-1],max(dp[i+1][j],dp[i][j-1]));}}return dp[1][size];}
};

132. 分割回文串 II

https://leetcode-cn.com/problems/palindrome-partitioning-ii/

参考解法：

https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/dong-tai-gui-hua-by-liweiwei1419-2/

https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/dong-tai-gui-hua-jie-fa-c-by-bike666222/

分割回文串的第一题是用回溯算法解决的，本题难度升级，我们需要使用动态规划，不同于上面两道题目的设法，那样太复杂了，本题dp这么定义：

我们下面看这么一种情况

base case要谨慎处理：

        //长度为n的字符，最多分割n-1次，以此作为base casefor(int i = 1;i<=size;++i)dp[i] = i-1;

核心代码：

        //本题的核心代码for(int i = 1;i<=size;++i){if(checkPalindrome[1][i]) {dp[i]=0;continue;}for(int j = 1;j<i;++j){//开始进行分割，0到j，j+1到i，检查j+1到i是不是回文，如果是，就切一刀if(checkPalindrome[j+1][i]) dp[i]=min(dp[i],dp[j]+1);}}

完整代码：

class Solution {
public:int minCut(string s) {int size = s.size();if(size == 0) return 0;vector<int>dp(size+1,0);//从1到i(前i个字符)，字符串分割为回文，需要最少的切割次数//长度为n的字符，最多分割n-1次，以此作为base casefor(int i = 1;i<=size;++i)dp[i] = i-1;//创建二维数组用于记录子串s[a:b]是否为回文串，且一开始全部初始化为false（可以发现a<=b）//此部分和5的核心代码是一样的vector<vector<bool>> checkPalindrome(size+1, vector<bool>(size+1, false));for(int i = 1;i<=size;++i) checkPalindrome[i][i] = true;//单个元素算回文for(int j = 1;j<=size;++j)//必须固定后限进行循环{for(int i = 1;i<=j;++i){if(s[i-1] == s[j-1]){if(j-i+1<=3) checkPalindrome[i][j] = true;else checkPalindrome[i][j] = checkPalindrome[i+1][j-1];}}}//本题的核心代码for(int i = 1;i<=size;++i){if(checkPalindrome[1][i]) {dp[i]=0;continue;}for(int j = 1;j<i;++j){//开始进行分割，0到j，j+1到i，检查j+1到i是不是回文，如果是，就切一刀if(checkPalindrome[j+1][i]) dp[i]=min(dp[i],dp[j]+1);}}return dp[size];}
};

730. 统计不同回文子字符串

https://leetcode-cn.com/problems/count-different-palindromic-subsequences/

https://leetcode-cn.com/problems/count-different-palindromic-subsequences/solution/tong-ji-bu-tong-hui-wen-zi-zi-fu-chuan-by-leetcode/

再次非常感谢上述内容提供者无私的分享！