算法训练营day57_动态规划（3.18提前写）

647.回文子串

求一个字符串中有多少个回文子串；

与以往不同，这里还套用前i个的话，找不到与i-1的递推关系；

• f(i,j)表示[i,j]子串是否为回文子串；

• 转移；如果s[i]==s[j]，看[i+1,j-1]，因为可能有交叉，需要分类讨论；

  ​ 如果i-j只有<=2个字符，那么肯定是回文的；

  ​ 如果i-j有>=3个字符，看f[i+1] [j-1]；

• 初始化；全为false;

• **遍历顺序；本题遍历顺序有讲究的！**之前习惯了从左到右；遍历顺序关键要把小状态提前算出来，故本题i需要倒序，j从左到右，还有个坑点就是j必须从i开始，因为区间[i,j]；

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

516.最长回文子序列

本题是最长回文子序列，与上题有些差别；状态表示+状态转移都想出来了，关键是初始化没想出来；

• f(i,j)表示[i,j]子序列最长回文子序列的 长度；

• 转移；如果s[i]==s[j]，=[i+1,j-1]+2；

  ​ 比较(i+1,j)与(i,j+1)；

• **初始化；比较关键，**全为false;i到j只有一个的话，初始化为true；

• **遍历顺序；**本题是从左下转移右上，故i是倒序，j是顺序；

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