大家好，首先感慨一下，时间过的真是快，不知不觉我们的训练营就已经到第五十天了，首先祝贺自己一直在坚持，今天是我们动态规划章节的收官之战，明天我们就会走进一个全新的算法章节单调栈，我们要为我们的动态规划章节画上一个完美的句号，那我们就开始我们今天的动态规划的题目。

第一题对应力扣编号为647的题目回文子串

        其实大家应该很熟悉什么叫回文子串了，就是倒着读和正着读是一样的，当然很明显一个字符的字符串当然是回文串，那今天的这道题目是什么意思呢？我们先一起来看一下：

        其实很明显题目是要求我们去求回文串的个数，我们就直接考虑使用动态规划的思路来解决这道题目，当然免不了要使用动规五部曲：

        第一步确定dp数组以及下标的含义：这道题目就有点不一样了，我们以前做过的绝大部分题目我们都是题目要求什么我们就定义什么，但是在这里我们如果还要定义dp[i] 为 下标i结尾的字符串有 dp[i]个回文串的话我们就会发现我们压根找不到递推关系，这样就不好了，没有递推关系我们可怎么解决这道题目？大家其实想想我们回文串dp[i]与dp[i-1]与dp[i+1]是否存在什么关系吗？好像是没有的，它们压根可以表示任意一个字符，而且还有回文串的长度也是不确定的，因此我们这时候去看回文串的关系示意图：

        我们的确使用一个变量跟本表示不了回文字符串，因此我们就需要考虑使用类似于双指针的思想，其实我们在写判断回文字符串的函数的时候我们也是会考虑使用双指针的思想来判断，因此我们可以这样判断回文串了，因此我们就可以找到合适的定义dp数组的方法，我们就可以这样定义：布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

       第二步确定递推公式，在确定递推公式时，就要分析如下几种情况。其实主要是两种情况，第一种情况当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。也就说明我们当前的字符串一定不是回文字符串，第二种情况大家需要仔细考虑就是s[i]与s[j]相等，首先第一种可能是下标i 与 j相同，同一个字符例如a，当然是回文子串，第二种可能是下标i 与 j相差为1，例如aa，也是回文子串，i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。以上所有的情况都必不可少。

      第三步就是初始化dp数组，dp[i][j]可以初始化为true么？ 当然不行，怎能刚开始就全都匹配上了。因此我们需要把dp[i][j] = false才可以。

      第四步确定遍历顺序，这个有点意思，我们还是得看一下dp数组的示意图：

        因此我们如果这矩阵是从上到下，从左到右遍历，那么会用到没有计算过的dp[i + 1][j - 1]，也就是根据不确定是不是回文的区间[i+1,j-1]，来判断了[i,j]是不是回文，那结果一定是不对的。我们需要一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。

        经过上述分析，我们就可以给出本题的解题代码：

class Solution {
public:int countSubstrings(string s) {//初始化dp数组vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));//存储回文字串的个数int result = 0;//遍历顺序for (int i = s.size() - 1; i >= 0; --i){for (int j = i; j < s.size(); ++j){if (s[i] == s[j]){if (j - i <= 1) result++, dp[i][j] = true;else if (dp[i + 1][j - 1]) result++, dp[i][j] = true;}}}return result;}
};

        这道题其实有点反常规操作，当然理解遍历顺序与定义dp数组的思想是关键，我们这道题就分享到这里，我们继续我们的下一道题目。

第二题对应力扣编号为516的题目最长的回文子序列

       这道题与上一道题目应该是类似的，还是回文子串的问题，我们先看一下题目要求：

        我们应该是返回最长的回文子序列的长度，而且其实我们是可以对原字符串进行删除操作的，其实就是告诉我们我们找到的回文字符串未必是连续的，我们就使用动规五部曲来解决这道题目：

      第一步确定dp数组以及下标的含义，dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

      第二步是确定递推公式，在判断回文子串的题目中，关键逻辑就是看s[i]与s[j]是否相同。如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;这个很明显，如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。这个理解起来有点难度，大家应该记得上一道题目的思路，加入s[j]的回文子序列长度为dp[i + 1][j]，加入s[i]的回文子序列长度为dp[i][j - 1]。那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])，其实我们还是进行了删除操作，感觉与前面的题目思路都有相似的地方，理解dp数组的含义很重要。

      第三步是初始化dp数组，首先要考虑当i 和j 相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。其实我们需要考虑的是当i与j相同，那么dp[i][j]一定是等于1的，其他情况dp[i][j]初始为0就行，这样递推公式：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不会被初始值覆盖。

      第四步就是确定遍历顺序，大家看下面的图： 

       我们就可以理解，所以遍历i的时候一定要从下到上遍历，这样才能保证下一行的数据是经过计算的。

     综合上述分析我们就可以给出答案：

class Solution {
public:int longestPalindromeSubseq(string s) {//定义dp数组vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));//dp数组的初始化for (int i = 0; i < s.size(); ++i) dp[i][i] = 1;//确定遍历顺序for (int i = s.size() - 1; i >= 0; --i){for (int j = i + 1; j < s.size(); ++j){if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;else dp[i][j] = max(dp[i + 1][j],dp[i][j - 1]);}}return dp[0][s.size() - 1];}
};

动态规划总结篇

        到这里我们就完成了动态规划的所有题目，其实动态规划的题目类型很多，我们刷了不少类型，我们也深刻理解了动规五部曲在解题中的巧妙使用，如果遇到问题大家可以这样想：我们如果想不清楚dp数组的具体含义，递归公式从何谈起，甚至初始化的时候就写错了。如果看过背包系列，特别是完全背包，那么两层for循环先后顺序绝对可以搞懵很多人，反而递归公式是简单的。背包问题要注意区分，我们的遍历顺序很重要，希望大家可以好好努力，多去理解，掌握任何一种算法都不简单，更何况是动态规划这种比较难的题目，我们今天的分享就到这里，我们明天的单调栈见！