【动态规划】代码随想录算法训练营第五十七天 |647. 回文子串， 516.最长回文子序列，动态规划总结篇（待补充）

墨蓝 2024-04-23 04:41 63阅读 0赞

## 647. 回文子串 ##

1、题目链接：[. - 力扣（LeetCode）][. - _LeetCode]

2、文章讲解：[代码随想录][Link 1]

3、题目：

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

*  输入："abc"
 *  输出：3
 *  解释：三个回文子串: "a", "b", "c"

示例 2：

*  输入："aaa"
 *  输出：6
 *  解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：输入的字符串长度不会超过 1000 。

4、视频链接：

[动态规划，字符串性质决定了DP数组的定义 | LeetCode：647.回文子串\_哔哩哔哩\_bilibili][DP_ _ LeetCode_647._bilibili]

class Solution {
        public int countSubstrings(String s) {
            boolean[][] dp = new boolean[s.length()][s.length()];
    
            int res = 0;
            for (int i = s.length() - 1; i >= 0; i--) {
                for (int j = i; j < s.length(); j++) {
                    if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])) {
                        res++;
                        dp[i][j] = true;
                    }
                }
            }
            return res;
        }
    }

## 516.最长回文子序列 ##

1、题目链接：[. - 力扣（LeetCode）][. - _LeetCode 1]

2、文章讲解：[代码随想录][Link 2]

3、题目：

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1: 输入: "bbbab" 输出: 4 一个可能的最长回文子序列为 "bbbb"。

示例 2: 输入:"cbbd" 输出: 2 一个可能的最长回文子序列为 "bb"。

提示：

*  1 <= s.length <= 1000
 *  s 只包含小写英文字母

4、视频链接：

[动态规划再显神通，LeetCode：516.最长回文子序列\_哔哩哔哩\_bilibili][LeetCode_516._bilibili]

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];
        }
    }

## 动态规划总结篇 ##

如今动态规划已经讲解了42道经典题目，共50篇文章，是时候做一篇总结了。

关于动态规划，在专题第一篇[关于动态规划，你该了解这些！(opens new window)][opens new window]就说了动规五部曲，**而且强调了五部对解动规题目至关重要！**

这是Carl做过一百多道动规题目总结出来的经验结晶啊，如果大家跟着「代码随想哦」刷过动规专题，一定会对这动规五部曲的作用感受极其深刻。

动规五部曲分别为：

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

动规专题刚开始的时候，讲的题目比较简单，不少录友和我反应：这么简单的题目 讲的复杂了，不用那么多步骤分析，想出递推公式直接就AC这道题目了。

**Carl的观点一直都是 简单题是用来 巩固方法论的**。 简单题目是可以靠感觉，但后面稍稍难一点的题目，估计感觉就不好使了。

在动规专题讲解中，也充分体现出，这动规五部曲的重要性。

还有不少录友对动规的理解是：递推公式是才是最难最重要的，只要想出递归公式，其他都好办。

**其实这么想的同学基本对动规理解的不到位的**。

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

*  如果想不清楚dp数组的具体含义，递归公式从何谈起，甚至初始化的时候就写错了。
 *  例如[动态规划：不同路径还不够，要有障碍！(opens new window)][opens new window 1]在这道题目中，初始化才是重头戏
 *  如果看过背包系列，特别是完全背包，那么两层for循环先后顺序绝对可以搞懵很多人，反而递归公式是简单的。
 *  至于推导dp数组的重要性，动规专题里几乎每篇Carl都反复强调，当程序结果不对的时候，一定要自己推导公式，看看和程序打印的日志是否一样。

好啦，我们再一起回顾一下，动态规划专题中我们都讲了哪些内容。

### [\#][Link 3]动态规划基础 ###

*  [关于动态规划，你该了解这些！(opens new window)][opens new window]
 *  [动态规划：斐波那契数(opens new window)][opens new window 2]
 *  [动态规划：爬楼梯(opens new window)][opens new window 3]
 *  [动态规划：使用最小花费爬楼梯(opens new window)][opens new window 4]
 *  [动态规划：不同路径(opens new window)][opens new window 5]
 *  [动态规划：不同路径还不够，要有障碍！(opens new window)][opens new window 1]
 *  [动态规划：整数拆分，你要怎么拆？(opens new window)][opens new window 6]
 *  [动态规划：不同的二叉搜索树(opens new window)][opens new window 7]

### [\#][Link 4]背包问题系列 ###

![535fada148881773c1383df2cff23d0f.png][]

*  [动态规划：关于01背包问题，你该了解这些！(opens new window)][01_opens new window]
 *  [动态规划：关于01背包问题，你该了解这些！（滚动数组）(opens new window)][01_opens new window 1]
 *  [动态规划：分割等和子集可以用01背包！(opens new window)][01_opens new window 2]
 *  [动态规划：最后一块石头的重量 II(opens new window)][II_opens new window]
 *  [动态规划：目标和！(opens new window)][opens new window 8]
 *  [动态规划：一和零！(opens new window)][opens new window 9]
 *  [动态规划：关于完全背包，你该了解这些！(opens new window)][opens new window 10]
 *  [动态规划：给你一些零钱，你要怎么凑？(opens new window)][opens new window 11]
 *  [动态规划：Carl称它为排列总和！(opens new window)][Carl_opens new window]
 *  [动态规划：以前我没得选，现在我选择再爬一次！(opens new window)][opens new window 12]
 *  [动态规划： 给我个机会，我再兑换一次零钱(opens new window)][_opens new window]
 *  [动态规划：一样的套路，再求一次完全平方数(opens new window)][opens new window 13]
 *  [动态规划：单词拆分(opens new window)][opens new window 14]
 *  [动态规划：关于多重背包，你该了解这些！(opens new window)][opens new window 15]
 *  [听说背包问题很难？ 这篇总结篇来拯救你了(opens new window)][_opens new window 1]

### [\#][Link 5]打家劫舍系列 ###

*  [动态规划：开始打家劫舍！(opens new window)][opens new window 16]
 *  [动态规划：继续打家劫舍！(opens new window)][opens new window 17]
 *  [动态规划：还要打家劫舍！(opens new window)][opens new window 18]

### [\#][Link 6]股票系列 ###

![621722fd49e02661a924eaca763ffdc2.jpeg][]

*  [动态规划：买卖股票的最佳时机(opens new window)][opens new window 19]
 *  [动态规划：本周我们都讲了这些（系列六）(opens new window)][opens new window 20]
 *  [动态规划：买卖股票的最佳时机II(opens new window)][II_opens new window 1]
 *  [动态规划：买卖股票的最佳时机III(opens new window)][III_opens new window]
 *  [动态规划：买卖股票的最佳时机IV(opens new window)][IV_opens new window]
 *  [动态规划：最佳买卖股票时机含冷冻期(opens new window)][opens new window 21]
 *  [动态规划：本周我们都讲了这些（系列七）(opens new window)][opens new window 22]
 *  [动态规划：买卖股票的最佳时机含手续费(opens new window)][opens new window 23]
 *  [动态规划：股票系列总结篇(opens new window)][opens new window 24]

### [\#][Link 7]子序列系列 ###

![6376685827fa1b33c7e01277be5f4284.jpeg][]

*  [动态规划：最长递增子序列(opens new window)][opens new window 25]
 *  [动态规划：最长连续递增序列(opens new window)][opens new window 26]
 *  [动态规划：最长重复子数组(opens new window)][opens new window 27]
 *  [动态规划：最长公共子序列(opens new window)][opens new window 28]
 *  [动态规划：不相交的线(opens new window)][opens new window 29]
 *  [动态规划：最大子序和(opens new window)][opens new window 30]
 *  [动态规划：判断子序列(opens new window)][opens new window 31]
 *  [动态规划：不同的子序列(opens new window)][opens new window 32]
 *  [动态规划：两个字符串的删除操作(opens new window)][opens new window 33]
 *  [动态规划：编辑距离(opens new window)][opens new window 34]
 *  [为了绝杀编辑距离，我做了三步铺垫，你都知道么？(opens new window)][opens new window 35]
 *  [动态规划：回文子串(opens new window)][opens new window 36]
 *  [动态规划：最长回文子序列(opens new window)][opens new window 37]

### [\#][Link 8]动规结束语 ###

关于动规，还有 树形DP（打家劫舍系列里有一道），数位DP，区间DP ，概率型DP，博弈型DP，状态压缩dp等等等，这些我就不去做讲解了，面试中出现的概率非常低。

能把本篇中列举的题目都研究通透的话，你的动规水平就已经非常高了。 对付面试已经足够！

![b4407d42b717332ca64a15254d3552af.png][]

这个图是 [代码随想录知识星球(opens new window)][opens new window 38]成员：[青(opens new window)][opens new window 39]，所画，总结的非常好，分享给大家。

这应该是全网对动规最深刻的讲解系列了。

**其实大家去网上搜一搜也可以发现，能把动态规划讲清楚的资料挺少的，因为动规确实很难！要给别人讲清楚更难！**

《剑指offer》上 动规的题目很少，经典的算法书籍《算法4》 没有讲 动规，而《算法导论》讲的动规基本属于劝退级别的。

讲清楚一道题容易，讲清楚两道题也容易，但把整个动态规划的各个分支讲清楚，每道题目讲通透，并用一套方法论把整个动规贯彻始终就非常难了。

[. - _LeetCode]: https://leetcode.cn/problems/palindromic-substrings/
[Link 1]: https://programmercarl.com/0647.%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[DP_ _ LeetCode_647._bilibili]: https://www.bilibili.com/video/BV17G4y1y7z9/
[. - _LeetCode 1]: https://leetcode.cn/problems/longest-palindromic-subsequence/
[Link 2]: https://programmercarl.com/0516.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E5%BA%8F%E5%88%97.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[LeetCode_516._bilibili]: https://www.bilibili.com/video/BV1d8411K7W6/
[opens new window]: https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
[opens new window 1]: https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html
[Link 3]: https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%80%BB%E7%BB%93%E7%AF%87.html#%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E5%9F%BA%E7%A1%80
[opens new window 2]: https://programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html
[opens new window 3]: https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html
[opens new window 4]: https://programmercarl.com/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.html
[opens new window 5]: https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html
[opens new window 6]: https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html
[opens new window 7]: https://programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
[Link 4]: https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%80%BB%E7%BB%93%E7%AF%87.html#%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%B3%BB%E5%88%97
[535fada148881773c1383df2cff23d0f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/bbb1fc241ec944aa9bf8099a72231c38.png
[01_opens new window]: https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html
[01_opens new window 1]: https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html
[01_opens new window 2]: https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html
[II_opens new window]: https://programmercarl.com/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.html
[opens new window 8]: https://programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html
[opens new window 9]: https://programmercarl.com/0474.%E4%B8%80%E5%92%8C%E9%9B%B6.html
[opens new window 10]: https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html
[opens new window 11]: https://programmercarl.com/0518.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2II.html
[Carl_opens new window]: https://programmercarl.com/0377.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C%E2%85%A3.html
[opens new window 12]: https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E7%89%88%E6%9C%AC.html
[_opens new window]: https://programmercarl.com/0322.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2.html
[opens new window 13]: https://programmercarl.com/0279.%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9%E6%95%B0.html
[opens new window 14]: https://programmercarl.com/0139.%E5%8D%95%E8%AF%8D%E6%8B%86%E5%88%86.html
[opens new window 15]: https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85.html
[_opens new window 1]: https://programmercarl.com/%E8%83%8C%E5%8C%85%E6%80%BB%E7%BB%93%E7%AF%87.html
[Link 5]: https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%80%BB%E7%BB%93%E7%AF%87.html#%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D%E7%B3%BB%E5%88%97
[opens new window 16]: https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html
[opens new window 17]: https://programmercarl.com/0213.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DII.html
[opens new window 18]: https://programmercarl.com/0337.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DIII.html
[Link 6]: https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%80%BB%E7%BB%93%E7%AF%87.html#%E8%82%A1%E7%A5%A8%E7%B3%BB%E5%88%97
[621722fd49e02661a924eaca763ffdc2.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/55aee13b70ba4fc0acff35d895ca2f73.jpeg
[opens new window 19]: https://programmercarl.com/0121.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA.html
[opens new window 20]: https://programmercarl.com/%E5%91%A8%E6%80%BB%E7%BB%93/20210225%E5%8A%A8%E8%A7%84%E5%91%A8%E6%9C%AB%E6%80%BB%E7%BB%93.html
[II_opens new window 1]: https://programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html
[III_opens new window]: https://programmercarl.com/0123.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAIII.html
[IV_opens new window]: https://programmercarl.com/0188.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAIV.html
[opens new window 21]: https://programmercarl.com/0309.%E6%9C%80%E4%BD%B3%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E6%97%B6%E6%9C%BA%E5%90%AB%E5%86%B7%E5%86%BB%E6%9C%9F.html
[opens new window 22]: https://programmercarl.com/%E5%91%A8%E6%80%BB%E7%BB%93/20210304%E5%8A%A8%E8%A7%84%E5%91%A8%E6%9C%AB%E6%80%BB%E7%BB%93.html
[opens new window 23]: https://programmercarl.com/0714.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA%E5%90%AB%E6%89%8B%E7%BB%AD%E8%B4%B9%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html
[opens new window 24]: https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92-%E8%82%A1%E7%A5%A8%E9%97%AE%E9%A2%98%E6%80%BB%E7%BB%93%E7%AF%87.html
[Link 7]: https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%80%BB%E7%BB%93%E7%AF%87.html#%E5%AD%90%E5%BA%8F%E5%88%97%E7%B3%BB%E5%88%97
[6376685827fa1b33c7e01277be5f4284.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/a1721969ea5a434b8da4d91650b21299.jpeg
[opens new window 25]: https://programmercarl.com/0300.%E6%9C%80%E9%95%BF%E4%B8%8A%E5%8D%87%E5%AD%90%E5%BA%8F%E5%88%97.html
[opens new window 26]: https://programmercarl.com/0674.%E6%9C%80%E9%95%BF%E8%BF%9E%E7%BB%AD%E9%80%92%E5%A2%9E%E5%BA%8F%E5%88%97.html
[opens new window 27]: https://programmercarl.com/0718.%E6%9C%80%E9%95%BF%E9%87%8D%E5%A4%8D%E5%AD%90%E6%95%B0%E7%BB%84.html
[opens new window 28]: https://programmercarl.com/1143.%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97.html
[opens new window 29]: https://programmercarl.com/1035.%E4%B8%8D%E7%9B%B8%E4%BA%A4%E7%9A%84%E7%BA%BF.html
[opens new window 30]: https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html
[opens new window 31]: https://programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html
[opens new window 32]: https://programmercarl.com/0115.%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97.html
[opens new window 33]: https://programmercarl.com/0583.%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C.html
[opens new window 34]: https://programmercarl.com/0072.%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB.html
[opens new window 35]: https://programmercarl.com/%E4%B8%BA%E4%BA%86%E7%BB%9D%E6%9D%80%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB%EF%BC%8C%E5%8D%A1%E5%B0%94%E5%81%9A%E4%BA%86%E4%B8%89%E6%AD%A5%E9%93%BA%E5%9E%AB.html
[opens new window 36]: https://programmercarl.com/0647.%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2.html
[opens new window 37]: https://programmercarl.com/0516.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E5%BA%8F%E5%88%97.html
[Link 8]: https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%80%BB%E7%BB%93%E7%AF%87.html#%E5%8A%A8%E8%A7%84%E7%BB%93%E6%9D%9F%E8%AF%AD
[b4407d42b717332ca64a15254d3552af.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/7cc0bb085f8945978340bae83fd67d06.png
[opens new window 38]: https://programmercarl.com/other/kstar.html
[opens new window 39]: https://wx.zsxq.com/dweb2/index/footprint/185251215558842