建设网站网站建设公司,做财经类新闻的网站,网站如何做快排,南宁建设厅网站语言
Java
647. 回文子串
回文子串
题目
给你一个字符串 s #xff0c;请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。 思路
动规五部曲来分析
1.dp数组的含义#x…语言
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.
总结
动态规划完结撒花
这个模块还需要多练多看。
继续加油
明天开始单调栈
患难及困苦是磨炼人格的学府
