刷题Day49|647. 回文子串、516.最长回文子序列
647. 回文子串
思路：递推公式的含义是[i, j]内的子串是否为回文子串（bolean[][])。一共两种情况：s[i] = s[j]，i和j相差1以外就得判断中间包含的的字符串是否为回文了，所以if (j - i <=1) dp[i][j] = true; else if(dp[i + 1][j - 1] == true) dp[i][j] = true; 反之s[i]和s[j]不等，那就一定不是回文字符串了，保持初始值false。
注意：遍历顺序是从下到上，从左往右。并且j一定要大于等于i。
516.最长回文子序列
思路：dp[i][j]表示[i, j]内的回文字符串长度。两种情况讨论，如果s[i] =s[j]，dp[i][j] = dp[i+1][j-1] +2; 否则就是i为头或者j为尾取最大值，dp[i][j] = max(dp[i+1][j], dp[i][j-1]）。遍历顺序是从下往上，从左到右。
注意：初始化的时候根据dp[i][j]的含义，i=j时dp[i][j]=1。
原文地址：https://blog.csdn.net/sanwanaaa/article/details/140360733
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！