赞
踩
- dp数组:dp[i][j]表示区间i~j之间是否为回文串
- 递推公式:
当s[i] == s[j]时,
若i == j,则此时肯定为回文子串,dp[i][j] = true;
若j - i = 1,则此时也为回文子串,dp[i][j] = true;
若j - i > 1,则需要判断i + 1 ~ j-1是否为回文串,即dp[i][j] = dp[i+1][j-1]是否为true;
当s[i] != s[j],则 dp[i][j] =false;
3.初始化, dp[i][j]初始化为false;- 遍历顺序,由递推公式可知dp[i][j]需由dp[i+1][j-1]推导而来。则遍历顺序为从下到上,从左到右。这样才可以保证dp[i+1][j-1都是经过计算了的。
- 推导dp数组。dp数组有几个true,就有几个回文子串。
注意dp[i][j]的定义,可以知道j一定是大于等于j的,故二维数组只有上半部分被计算了。
class Solution { public: int countSubstrings(string s) { //dp[i][j]表示区间i~j是否为回文子串 vector<vector<bool> > dp(s.size() + 1, vector<bool>(s.size() + 1)); int res = 0; for(int i = s.size(); i >= 1; i--){ for(int j = i; j <= s.size(); j++){ if(s[i-1] == s[j-1]){ if(j - i <= 1){ dp[i][j] = true; res++; } else{ if(dp[i+1][j-1]){ dp[i][j] = true; res++; } } } else{ dp[i][j] = false; } } } return res; } };
- 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] = max(dp[i][j-1], dp[i+1][j])
class Solution { public: int longestPalindromeSubseq(string s) { vector<vector<int> > dp(s.size() + 1, vector<int>(s.size() + 1, 0)); for(int i = 1; i <= s.size(); i++) dp[i][i] = 1; for(int i = s.size()-1 ; i >= 1; i--){ for(int j = i + 1 ; j <= s.size(); j++){ if(s[i-1] == s[j-1]){ dp[i][j] = dp[i+1][j-1] + 2; } else{ dp[i][j] = max(dp[i][j-1], dp[i+1][j]); } } } return dp[1][s.size()]; } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。