手机网站做静态路径刷粉网站推广免费
语言
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.
总结
动态规划完结撒花！！
这个模块还需要多练，多看。
继续加油
明天开始单调栈