代码随想录算法训练营29期|day60 任务以及具体安排

本文主要是介绍代码随想录算法训练营29期|day60 任务以及具体安排，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第九章动态规划part17

647. 回文子串

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

思路：dp数组表示[i,j]是否为回文串，递推公式：如果i和j相等，有三种情况，i==j，就直接赋值为true，如果j=i+1, 同理，如果j>i+1，判断dp[i+1][j-1]是否为true。遍历顺序为从下到上，从左到右，最后返回result。

516.最长回文子序列

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

思路：该题与上一题的区别在于该题不需要连续，dp数组表示[i,j]最大的回文子序列的数量，递推公式：如果i，j相等，直接在dp[i+1][j-1]上+2，如果不相等，就比较取最大值。初始化要把i和j相等的情况初始为1。

动态规划最强总结篇！

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

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

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

动规五部曲分别为：
确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组
动规专题刚开始的时候，讲的题目比较简单，不少录友和我反应：这么简单的题目讲的复杂了，不用那么多步骤分析，想出递推公式直接就AC这道题目了。

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

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

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

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

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

#动态规划基础
关于动态规划，你该了解这些！(opens new window)
动态规划：斐波那契数(opens new window)
动态规划：爬楼梯(opens new window)
动态规划：使用最小花费爬楼梯(opens new window)
动态规划：不同路径(opens new window)
动态规划：不同路径还不够，要有障碍！(opens new window)
动态规划：整数拆分，你要怎么拆？(opens new window)
动态规划：不同的二叉搜索树(opens new window)
#背包问题系列
动态规划：关于01背包问题，你该了解这些！(opens new window)
动态规划：关于01背包问题，你该了解这些！（滚动数组）(opens new window)
动态规划：分割等和子集可以用01背包！(opens new window)
动态规划：最后一块石头的重量 II(opens new window)
动态规划：目标和！(opens new window)
动态规划：一和零！(opens new window)
动态规划：关于完全背包，你该了解这些！(opens new window)
动态规划：给你一些零钱，你要怎么凑？(opens new window)
动态规划：Carl称它为排列总和！(opens new window)
动态规划：以前我没得选，现在我选择再爬一次！(opens new window)
动态规划：给我个机会，我再兑换一次零钱(opens new window)
动态规划：一样的套路，再求一次完全平方数(opens new window)
动态规划：单词拆分(opens new window)
动态规划：关于多重背包，你该了解这些！(opens new window)
听说背包问题很难？这篇总结篇来拯救你了(opens new window)
#打家劫舍系列
动态规划：开始打家劫舍！(opens new window)
动态规划：继续打家劫舍！(opens new window)
动态规划：还要打家劫舍！(opens new window)
#股票系列
动态规划：买卖股票的最佳时机(opens new window)
动态规划：本周我们都讲了这些（系列六）(opens new window)
动态规划：买卖股票的最佳时机II(opens new window)
动态规划：买卖股票的最佳时机III(opens new window)
动态规划：买卖股票的最佳时机IV(opens new window)
动态规划：最佳买卖股票时机含冷冻期(opens new window)
动态规划：本周我们都讲了这些（系列七）(opens new window)
动态规划：买卖股票的最佳时机含手续费(opens new window)
动态规划：股票系列总结篇(opens new window)
#子序列系列
动态规划：最长递增子序列(opens new window)
动态规划：最长连续递增序列(opens new window)
动态规划：最长重复子数组(opens new window)
动态规划：最长公共子序列(opens new window)
动态规划：不相交的线(opens new window)
动态规划：最大子序和(opens new window)
动态规划：判断子序列(opens new window)
动态规划：不同的子序列(opens new window)
动态规划：两个字符串的删除操作(opens new window)
动态规划：编辑距离(opens new window)
为了绝杀编辑距离，我做了三步铺垫，你都知道么？(opens new window)
动态规划：回文子串(opens new window)
动态规划：最长回文子序列(opens new window)
#动规结束语

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

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

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

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

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