Day41 | 647. 回文子串 516.最长回文子序列

语言

Java

647. 回文子串

回文子串

题目

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

思路

动规五部曲来分析

1.dp数组的含义：

从i到j是否是回文子串，是的话就为true

2. 递推公式：
从字串内部推出，外部是否可以是回文子串

dp[i + 1][j - 1]如果为true

3.初始化：

初始化全为false

4.遍历顺序：

本题的遍历顺序是从下到上，从左到右

5.举例推导是否正确

代码

class Solution {public int countSubstrings(String s) {char[] chars = s.toCharArray();int len = chars.length;boolean dp[][] = new boolean[len][len];int res = 0;for (int i = len - 1; i >= 0; i--) {for (int j = i; j < len; j++) {if (chars[i] == chars[j]) {if (j - i <= 1) {dp[i][j] = true;res++;} else if (dp[i + 1][j - 1]) {res++;dp[i][j] = true;}}}}return res;}
}

易错点

这题的易错点在于遍历顺序

要从下到上从左到右。且j的初始值为i

516.最长回文子序列 

最长回文子序列 

题目

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

思路

动规五部曲

1.dp数组的含义：

代表从i到j最多的数

2.递推公式：
分为首字母与尾字母是否相等两种情况

相等时： dp[i][j] = dp[i + 1][j - 1] + 2;

不相等时：dp[i][j] = Math.max(dp[i][j], Math.max(dp[i + 1][j], dp[i][j - 1]));

3.初始化：

在i与j相等的时候初始化为1

4.遍历顺序

从下到上，从左到右

5.举例推导数组并打印

代码

class Solution {public int longestPalindromeSubseq(String s) {int len = s.length();int[][] dp = new int[len + 1][len + 1];for (int i = len - 1; i >= 0; i--) {dp[i][i] = 1;for (int j = i + 1; j < len; j++) {if (s.charAt(i) == s.charAt(j)) {dp[i][j] = dp[i + 1][j - 1] + 2;} else {dp[i][j] = Math.max(dp[i][j], Math.max(dp[i + 1][j], dp[i][j - 1]));}}}return dp[0][len - 1];}
}

易错点

易错点在于初始化当i与j相等的时候初始化为1.

总结

动态规划完结撒花！！

这个模块还需要多练，多看。

继续加油

明天开始单调栈

患难及困苦，是磨炼人格的学府