关于申请网站建设,管理网站怎么做的,国家示范院校建设网站,微信小程序怎么制作游戏647. 回文子串 这个题的dp定义想不到#xff0c;递推公式也想不到但是看题解都很容易理解#xff0c;遍历顺序不太好理解。 class Solution {
public:int countSubstrings(string s) {vectorvectorbool dp(s.size(), vectorbool(s.size(), false)… 647. 回文子串 这个题的dp定义想不到递推公式也想不到但是看题解都很容易理解遍历顺序不太好理解。 class Solution {
public:int countSubstrings(string s) {vectorvectorbool dp(s.size(), vectorbool(s.size(), false));int result 0;for (int i s.size() - 1; i 0; i--) {//i 1 为竖直方向加一 j-1为水平方向 这个是从底往上for (int j i; j s.size(); j) { //这个是水平方向从左往右由于dp数组的定义是dp[i][j]表示区间范围[i,j] 注意是左闭右闭的子串是否是回文子串如果是dp[i][j]为true否则为false。所以j一定要从i开始遍历if (s[i] s[j]) {if (j - i 1) { // 情况一 和 情况二result;dp[i][j] true;} else if (dp[i 1][j - 1]) { // 情况三result;dp[i][j] true; //这里的true与false就是0和1然后累加这个过程中的0和1得到最后的result}} }}return result;}
}; 516.最长回文子序列 回文子串是要连续的回文子序列可不是连续的遍历顺序先下后上先走后右
