刷题Day49|647. 回文子串、516.最长回文子序列

647. 回文子串

647. 回文子串 - 力扣（LeetCode）

思路：递推公式的含义是[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.最长回文子序列

516. 最长回文子序列 - 力扣（LeetCode）

思路：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。