#516 最长回文子序列(动态规划)
但是这次dp保存的不是是否为回文串，而是i->j可组成的最长回文子序列长度
状态转移：max(左，右，左下+2（如果s[i]==s[j])）
class Solution {
public:
int longestPalindromeSubseq(string s) {
int N=s.size();
vector<vector<int>> dp(N,vector<int>(N,0));
for(int i=0;i<N;i++) dp[i][i]=1;
for(int i=0;i<N-1;i++)
if(s[i]==s[i+1]) dp[i][i+1]=2;
else dp[i][i+1]=1;
for(int step=2;step<N;step++){
for(int i=0;i+step<N;i++){
int left=dp[i][i+step-1];
int down=dp[i+1][i+step];
int corn=dp[i+1][i+step-1]+2*(s[i]==s[i+step]);
if(left>=down && left>=corn) dp[i][i+step]=left;
else if(down>=corn) dp[i][i+step]=down;
else dp[i][i+step]=corn;
}
}
return dp[0][N-1];
}
};