647. 回文子串
一开始我想的dp[i]表示到i为止有多少回文子串，但返现这样推到不出任何dp之间的关系。
而如果把dp[i][j]定义为i到j之间是否是回文子串的话。
则dp[i][j]和dp[i+1][j-1]是有关系的。
if(s[i]==s[j]&&j-i>=0){if(j-i<=1){dp[i][j]=true;}else{if(dp[i+1][j-1])dp[i][j]=true;}
}
注意到此时它依赖的是矩阵中左下角的dp所以遍历顺序是从左到右，从下至上。
因为要保证j一定>=i，所以初始化时j=i
for(int i=n-1;i>=0;i--){for(int j=i;j<n;j++){
516.最长回文子序列
如果i和j相等，那就是dp[i+1][j-1]+2.
如果不相等，则从dp[i+1][j]和dp[i][j-1]中选择一个
class Solution {
public:int longestPalindromeSubseq(string s) {int n=s.size();vector<vector<int>> dp(n,vector<int>(n,1));for(int i=n-1;i>=0;i--){for(int j=i+1;j<n;j++){if(s[i]==s[j]){if(j-i>1)dp[i][j]=dp[i+1][j-1]+2;elsedp[i][j]=2;}elsedp[i][j]=max(dp[i][j-1],dp[i+1][j]);}}return dp[0][n-1];}
};
这里我和代码随想录的初始化方式不同，我直接把所有初始化成1了，所以要单独讨论两个相邻的i和j相等的情况，把它搞成2.