代码随想录算法训练营第五十六天 | 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. 最长回文子序列
相关文章
|
1月前
|
存储 算法
深入了解动态规划算法
深入了解动态规划算法
57 1
|
1月前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
1月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
38 0
|
10天前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
9天前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
26 2
|
1月前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
65 2
动态规划算法学习三:0-1背包问题
|
1月前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
65 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
1月前
|
算法
动态规划算法学习二:最长公共子序列
这篇文章介绍了如何使用动态规划算法解决最长公共子序列(LCS)问题,包括问题描述、最优子结构性质、状态表示、状态递归方程、计算最优值的方法,以及具体的代码实现。
118 0
动态规划算法学习二:最长公共子序列
|
1月前
|
存储 人工智能 算法
【算法——动态规划】蓝桥ALGO-1007 印章(C/C++)
【算法——动态规划】蓝桥ALGO-1007 印章(C/C++)
【算法——动态规划】蓝桥ALGO-1007 印章(C/C++)
|
1月前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
101 0