算法打卡：第九章 动态规划part13
今日劳绩：回文子串，最长回文子序列1. 回文子串
标题链接：647. - 力扣（LeetCode）
思路：
（1）dp数组的界说不再是标题的要求，而是二维的，下标 i 和 j 表示字符串对应下标的子串是不是回文串。再使用变量记录回文子串的个数
（2）初始化全为0
（3）如果当前两个字符相等，判定长度是否为0或1，满足要求则都是回文子串；如果长度大于1，那么下标向中间聚拢，如果仍然是回文子串，记录个数。
（4）遍历次序：依据递推公式，需要下标向中间聚拢也就是左下角的值推出当前值，所以需要从上到下从左到右遍历。
方法：
class Solution {
public int countSubstrings(String s) {
int len=s.length();
int result=0;
// 字符串中从 i 到 j 的子串是不是回文串
boolean[][] dp=new boolean;
// 初始化
for (int i=0;i<len;i++){
for (int j=0;j<len;j++){
dp=false;
}
}
// 从底向上，从左到右
for (int i=len-1;i>=0;i--){
for (int j=i;j<len;j++){
if (s.charAt(i)==s.charAt(j)){
if (j-i<=1){
dp=true;
result++;
}else {
dp=dp;// 向中间靠拢
if (dp==true){
result++;
}
}
}
}
}
return result;
}
} 2. 最长回文子序列
标题链接：516. - 力扣（LeetCode）
思路：
（1）dp数组表示 i 和 j 下标范围内的最长回文子序列长度
（2）初始化：递推公式不包罗长度为1的回文子串，所以二维数组的对角线元素全为1
（3）递推公式：如果 i 和 j 下标上的字符相等，那么回文子序列的长度在内层子串的基础上加2；如果不相等，则取分别加上左边的字符和右边的字符中的最大值。
（4）遍历次序：从递推公式可以看出来，当前位置依靠于左，左下，下的元素值，所以是从下到上，从左到右遍历。
方法：
class Solution {
public int longestPalindromeSubseq(String s) {
int len=s.length();
// 设置为len+1，初始化较为简单
int[][] dp=new int;
for (int i=len-1;i>=0;i--){
dp=1;
for (int j=i+1;j<len;j++){
if (s.charAt(i)==s.charAt(j)){
dp=dp+2;
}else {
dp=Math.max(dp,dp);
}
}
}
return dp;
}
} 总结：
（1）子序列和子串的区别在于，子序列可以删除元素，如果可以删除的环境不止一个就需要取此中的最大值。
（2）如果不能确定遍历次序，可以根据递推公式，分析dp数组中当前位置的值由哪些方向的值推导出来。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]