代码随想录算法训练营day46|动态规划part12

今天就结束动态规划章节了，以后还要多加练习。

今天的两道题都很有难度，647回文子串的思路非常巧妙，因为用一维dp数组比较难表示子串的起点和终点，所以需要用二维dp数组表示，dp[i][j]表示以i为起点，j为终点的子串是不是回文子串，当s[i]和s[j]不同时，该子串不是回文子串；当s[i]==s[j]时，分类讨论：如果该子串的长度为1或2，则该子串就是回文子串，若该子串长度＞2，则如果[i+1,j-1]是回文子串，则[i,j]，也是回文子串；

另外要注意的一点是这题的遍历顺序，因为dp[i][j]可能由左下角的值推导而来，所以需要从下往上，从左到右推导；

516最长回文子序列看起来好像和647回文子串很不一样，因为这题不是连续的子串而是中间可以有间隔，但是递推的思想其实是差不多的。同样定义二维dp数组，dp[i][j]表示以i为起点，j为终点中最长子串的长度，所以当s[i]==s[j]时，dp[i][j]=dp[i+1][j-1]+2;当s[i]!=s[j]时，dp[i][j]就取dp[i][j-1]和dp[i+1][j]的最大值。对于初始化，因为单个的字符是回文子串，所以dp[i][i]=1,其它的部分就初始化为0。

647. 回文子串

代码随想录

516.最长回文子序列

代码随想录

动态规划总结篇

代码随想录