代码随想录算法训练营第五十六天 | LeetCode 647. 回文子串、516. 最长回文子序列、动态规划总结

简介: 代码随想录算法训练营第五十六天 | LeetCode 647. 回文子串、516. 最长回文子序列、动态规划总结

代码随想录算法训练营第五十六天 | LeetCode 647. 回文子串、516. 最长回文子序列、动态规划总结

文章链接:回文子串最长回文子序列动态规划总结

视频链接:回文子串最长回文子序列

1. LeetCode 647. 回文子串

.1 思路

  1. 本题是给个字符串 s 求里面有多少个回文子串,单独一个元素也是回文子串
  2. dp 数组及其下标的含义:本题如果以 dp[i] 为下标 i 为结尾的字符串有 dp[i] 个回文串的话很难发现递推关系,很难看出和 dp[i-1] 或者 dp[i+1] 有什么关系。我们判断一个长度为 5 的元素时,如果范围 [1,3] 已经是回文的了,那么我们再判断 0 和 4 下标是否为回文就是了,也就是判断一个范围 [i,j] 是否为回文子串依赖于范围 [i+1,j-1] 是否为回文子串。因此定义二维数组 dp[i][j] 表示区间左闭右闭 [i,j] 是否为回文子串,是的话为 true,否则为 false。并且定义个变量 result 记录有多少个回文子串
  3. 递推公式:根据 dp 数组,我们判断两边的元素是否相同,如果相同就可以重复依赖于中间计算过的结果,i 是<=j 的,if(s[i]s[j])情况 1,ij,指向的是同一个元素,只有一个元素作为子串,比如 a,那这个也是回文子串;情况 2:i 和 j 相差 1,也就是相邻的,就是两个元素,比如 aa,那这个也是回文子串;情况 3:j-i>1,之间有很多元素,就要看 i+1 和 j-1 是否为回文子串,也就是依赖 dp[i+1][j-1] 是否为 true,如果是,那么这一段也是回文子串。if(j-i<=1)dp[i][j]=true,result++,这里就是情况 1 和 2;else if(dp[i+1][j-1]==true)dp[i][j]=true,result++,这里就是情况 3。这里为什么不讨论 s[i]!=s[j] 的情况呢?不相同就是默认 false 咯
  4. dp 数组的初始化:我们定义的是布尔类型的 dp 数组,默认全为 false 即可,为 true 就错了 436a544cb3324cc0ae1453018916e9a3.png
  5. 遍历顺序:根据递推公式得到推导方向,我们计算 dp[i][j] 时是需要 dp[i+1][j-1] 的值,因此遍历顺序要从下往上从左往右。for(int i=s.length()-1;i>=0;i–)for(int j=i;j<s.length();j++)j 为什么从 i 后面开始,因为我们的递推公式中 j 一定比 i 大。最终结果是 result
  6. 打印 dp 数组:用于 debug
  7. 双指针:本题也可以用双指针,一个指向中心,另一个向两边扩散,判断是否为回文子串

1.2 代码

class Solution {
    public int countSubstrings(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        boolean[][] dp = new boolean[len][len];
        int result = 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) { // 情况一 和 情况二
                        result++;
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { //情况三
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }
}


2. LeetCode 516. 最长回文子序列

2.1 思路

  1. 本题是给一个字符串求一个最长的回文子序列的长度,注意是子序列,也就是不要求连续的,在647. 回文子串中是子串,要求连续,比方说本题里“bbbab”的最长回文子序列是“bbbb”,长度是 4。
  2. dp 数组及其下标的含义:在647. 回文子串中讲解过为什么要利用二维数组,判断 [i,j] 范围是否为回文子串是要依赖于 [i+1,j-1]。dp[i][j] 表示 [i,j] 的回文子序列的长度为 dp[i][j]
  3. 递推公式:if(s[i]==s[j])dp[i][j],先看看里面的范围也就是 [i+1,j-1] 范围内的最长回文子序列的长度就是 dp[i+1][j-1],因此 dp[i][j] 就是在这基础上+2。如果不相同 else 就不能同时把两个元素加进来了,就要分别考虑两个元素,先考虑 s[i],如果加入里面的范围里,就变为了 [i,j-1] 的最长回文子序列的长度就是 dp[i,j-1],如果考虑 s[j],那就是变为了 [i+1,j] 的最长回文子序列的长度就是 dp[i+1,j],因此 dp[i][j]=Math.max(dp[i,j-1],dp[i+1,j])
  4. dp 数组的初始化:i 是一直+1 往中间移动,j 是一直-1 往中间移动,一直移动到最中间的位置,也就是 ij 指向同一个元素,这个情况是递推公式没有考虑到的,需要初始化的,指向同一个元素的最长回文子序列长度就是 1 了,即 dp[i][i]=1,这里写成两个 i 是为了体现相同位置,也就是 ij 的情况就初始化为 1 即可。for(int i=0;i<s.length();i++)dp[i][i]=1 b7635faf48d5423b985fc969e05b4cfc.png
  5. 遍历顺序:根据递推公式得到推导方向,因此我们的遍历方向是从下往上从左往右,for(int i=s.length();i>=0;i–)for(int j=i+1;j<s.length();j++)j 为什么从 i 后面开始,因为我们的递推公式中 j 一定比 i 大;j 为什么要比 i 大 1 啊,因为 j==i 的情况初始化时已经处理过了,直接从 i+1 开始。这里两层 for 循环可以颠倒吗?不可以,因为 j 是依赖于 i 的,j 一定大于等于 i 的,颠倒了就控制不了 j>=i 了,因此要先明确了 i 的范围才能明确 j 的范围。最终结果是在 dp[0][s.length()-1] 也就是右上方的位置
  6. 打印 dp 数组:用于 debug

2.2 代码

public 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 + 1][j], Math.max(dp[i][j], dp[i][j - 1]));
                }
            }
        }
        return dp[0][len - 1];
    }
}


3. 动态规划总结

动规五部曲分别为:

1. 确定dp数组(dp table)以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

动规五部曲里,哪一部没想清楚,这道题目基本就做不出来,即使做出来了也没有想清楚,而是朦朦胧胧的就把题目过了。

  • 如果想不清楚dp数组的具体含义,递归公式从何谈起,甚至初始化的时候就写错了。
  • 例如63. 不同路径 II这道题目中,初始化才是重头戏
  • 如果看过背包系列,特别是完全背包,那么两层for循环先后顺序绝对可以搞懵很多人,反而递归公式是简单的。
  • 至于推导dp数组的重要性,当程序结果不对的时候,一定要自己推导公式,看看和程序打印的日志是否一样。

3.1 动态规划基础

  1. 动态规划五部曲
  2. 509. 斐波那契数
  3. 70. 爬楼梯
  4. 746. 使用最小花费爬楼梯
  5. 62. 不同路径
  6. 63. 不同路径 II
  7. 343. 整数拆分
  8. 96. 不同的二叉搜索树

3.2 背包问题

3.2.1 01背包
  1. 01背包理论基础
  2. 01背包理论基础(滚动数组)
  3. 416. 分割等和子集
  4. 1049. 最后一块石头的重量 II
  5. 494. 目标和
  6. 474. 一和零
3.2.2 完全背包
  1. 完全背包理论基础
  2. 518. 零钱兑换 II
  3. 377. 组合总和 Ⅳ
  4. 70. 爬楼梯
  5. 322. 零钱兑换
  6. 279. 完全平方数
  7. 139. 单词拆分
3.2.3 多重背包
  • 多重背包理论基础
3.2.4 背包问题总结

3.3 打家劫舍系列

  1. 198. 打家劫舍
  2. 213. 打家劫舍 II
  3. 337. 打家劫舍 III

3.4 买卖股票系列

  1. 121. 买卖股票的最佳时机
  2. 122. 买卖股票的最佳时机 II
  3. 123. 买卖股票的最佳时机 III
  4. 188. 买卖股票的最佳时机 IV
  5. 309. 买卖股票的最佳时机含冷冻期
  6. 714. 买卖股票的最佳时机含手续费
  7. 买卖股票总结

3.5 子序列系列

3.5.1 子序列(不连续)
  1. 300. 最长递增子序列
  2. 674. 最长连续递增序列
  3. 718. 最长重复子数组
3.5.2 子序列(连续)
  1. 1143. 最长公共子序列
  2. 1035. 不相交的线
  3. 53. 最大子数组和
3.5.3 编辑距离
  1. 392. 判断子序列
  2. 115. 不同的子序列
  3. 583. 两个字符串的删除操作
  4. 72. 编辑距离
3.5.4 回文
  1. 647. 回文子串
  2. 516. 最长回文子序列
相关文章
|
4天前
leetcode代码记录(动态规划基础题(斐波那契数列)
leetcode代码记录(动态规划基础题(斐波那契数列)
10 0
|
4天前
|
存储 算法
Leetcode 30天高效刷数据结构和算法 Day1 两数之和 —— 无序数组
给定一个无序整数数组和目标值,找出数组中和为目标值的两个数的下标。要求不重复且可按任意顺序返回。示例:输入nums = [2,7,11,15], target = 9,输出[0,1]。暴力解法时间复杂度O(n²),优化解法利用哈希表实现,时间复杂度O(n)。
22 0
|
4天前
[leetcode~数位动态规划] 2719. 统计整数数目 hard
[leetcode~数位动态规划] 2719. 统计整数数目 hard
|
4天前
|
算法
代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形
代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形
23 3
|
4天前
|
存储 算法
代码随想录算法训练营第五十九天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
代码随想录算法训练营第五十九天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
22 1
|
4天前
|
算法
代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
18 3
|
4天前
|
算法 数据安全/隐私保护 计算机视觉
基于二维CS-SCHT变换和LABS方法的水印嵌入和提取算法matlab仿真
该内容包括一个算法的运行展示和详细步骤,使用了MATLAB2022a。算法涉及水印嵌入和提取,利用LAB色彩空间可能用于隐藏水印。水印通过二维CS-SCHT变换、低频系数处理和特定解码策略来提取。代码段展示了水印置乱、图像处理(如噪声、旋转、剪切等攻击)以及水印的逆置乱和提取过程。最后,计算并保存了比特率,用于评估水印的稳健性。
|
1天前
|
算法
m基于BP译码算法的LDPC编译码matlab误码率仿真,对比不同的码长
MATLAB 2022a仿真实现了LDPC码的性能分析,展示了不同码长对纠错能力的影响。短码长LDPC码收敛快但纠错能力有限,长码长则提供更强纠错能力但易陷入局部最优。核心代码通过循环进行误码率仿真,根据EsN0计算误比特率,并保存不同码长(12-768)的结果数据。
19 9
m基于BP译码算法的LDPC编译码matlab误码率仿真,对比不同的码长
|
2天前
|
算法
MATLAB|【免费】融合正余弦和柯西变异的麻雀优化算法SCSSA-CNN-BiLSTM双向长短期记忆网络预测模型
这段内容介绍了一个使用改进的麻雀搜索算法优化CNN-BiLSTM模型进行多输入单输出预测的程序。程序通过融合正余弦和柯西变异提升算法性能,主要优化学习率、正则化参数及BiLSTM的隐层神经元数量。它利用一段简单的风速数据进行演示,对比了改进算法与粒子群、灰狼算法的优化效果。代码包括数据导入、预处理和模型构建部分,并展示了优化前后的效果。建议使用高版本MATLAB运行。
|
4天前
|
算法 计算机视觉
基于高斯混合模型的视频背景提取和人员跟踪算法matlab仿真
该内容是关于使用MATLAB2013B实现基于高斯混合模型(GMM)的视频背景提取和人员跟踪算法。算法通过GMM建立背景模型,新帧与模型比较,提取前景并进行人员跟踪。文章附有程序代码示例,展示从读取视频到结果显示的流程。最后,结果保存在Result.mat文件中。