LeetCode

动态规划算法题型总结

动态规划算法题型总结

难度分类

简单

[3-70爬楼梯](LeetCode 70 爬楼梯.md) [2-62不同路径](LeetCode 62 不同路径.md)

中等

[5-198打家劫舍](LeetCode 198 打家劫舍.md) [1-53最大子数组和](LeetCode 53 最大子数组和 - 动态规划解法.md) [LCR095最长子序列](LCR 095 最长公共子序列.md) [8-416分割等和子集](LeetCode 416 分割等和子集.md) [12-1049最后一块石头的重量Ⅱ](LeetCode 1049 最后一块石头的重量 II.md) [10-494目标和](LeetCode 494 目标和.md) [9-474零和一](LeetCode 474 一和零.md) [14-978最长湍流子数组](LeetCode 978 最长湍流子数组.md) 中等偏上 [15-1546和为目标值且不重叠的子数组的最大数目](LeetCode 1546 和为目标值且不重叠的子数组的最大数目.md)

困难

滑窗优化dp [16-1871跳跃游戏VII](LeetCode 1871 跳跃游戏 VII.md)

类型分类

背包

[8-416分割等和子集](LeetCode 416 分割等和子集.md) [12-1049最后一块石头的重量Ⅱ](LeetCode 1049 最后一块石头的重量 II.md) [10-494目标和](LeetCode 494 目标和.md) [9-474零和一](LeetCode 474 一和零.md) [11-518零钱兑换](LeetCode 518 零钱兑换 II.md) [6-279完全平方数](LeetCode 279 完全平方数.md)

  • 零钱兑换: 我们的helper在不能找到可行解时不要返回-1 而是 Integer.MAX

子序列，子集

[LCR095最长子序列](LCR 095 最长公共子序列.md) [1-53最大子数组和](LeetCode 53 最大子数组和 - 动态规划解法.md)

分割问题

[4-139单词拆分](LeetCode 139 单词拆分.md) ：回溯转为dp。

北航课程

灵茶山艾府

动态规划和记忆化递归

  • 2026年1月29日15:20:39，由递归转动规时，递归参数越少越好，内部可以用循环

https://blog.csdn.net/weixin_43868339/article/details/122838956

在动态规划I中我们讲到，如果直接采用暴力迭代的方法，时间复杂度会非常高，和暴力穷举区别不大，原因在于迭代过程会产生大量的重复计算，为了避免重复计算，我们前面采取的办法都是从终点向起点倒推，计算所有状态的价值函数，倒推到起点，就能求解出状态转移方程。

当然，在某些情况下这也不是最优的解法，因为不是所有状态的价值函数都需要计算，也就是说，可能存在“多余计算”的问题。此时，我们不如就按照状态转移方程进行递归，已经计算过的一些价值函数的值储存起来以避免重复计算，这样我们就可以在计算最少的价值函数的情况下求解状态转移方程。这是一种从起点到终点的计算方法，最差情况是需要计算全部的价值函数，但如果我们有一些原则可以排除不可能的路径，那需要计算的价值函数的数量就大大减少。计算全部价值函数的实现方法我们称为狭义的动态规划，后面简称为动态规划。动态规划和记忆化搜索都是动态规划算法的实现方法，各有利弊。

也就是说：递归（不记忆化）不会计算不需要的值，但可能重复计算；动态规划可能计算不需要的值，但所有的值只会计算一次。

方法

  • 有的问题是备忘递归转变而来，例如 [5-198打家劫舍](LeetCode 198 打家劫舍.md)
  • 在想递归时，要想可能的情况，要想路径的可能情况， 而非最后的值。[LCR095最长子序列](LCR 095 最长公共子序列.md) 的回溯算法，想值可能不好想，但是我们假设构造 lcs数组的值就一下子好想了。
  • 有的问题不容易想到递归，例如[1-53最大子数组和](LeetCode 53 最大子数组和 - 动态规划解法.md)，这里的想不到是：使用递归求解的问题并不直接是题目的问题（我们可以求从1开始的最大子数组，进而递归地求从2、 从3、 从4 .。。开始的最大子数组，直到把从{index =1-end} 都遍历一遍，得到从所有位置开始最大子数组，求最大值就是答案。）这显然和看到题目之后能想到的思路相差甚远。
    • 求解问题为 最大子数组，思考这个子数组的可能情况，其起始位置只有n-1种可能，求出从 n-1种位置开始的最大子数组，再求最大。先列举有限种可能情况，每种情况各自找到最大，最后再在所有情况种找最大。
  • 这里的思考过程是倒过来的：有点分治的意思，求最后的解分为求从每个位置开始的最优解，再合：求最大即可。关键在于怎么分：最后球的是数组，数组有基础属性：开始，结束，。。，按开始分，或按结束分，以1开始的有很多：12 123 1234等等；分完之后求每个位置的最优解；再合。
  • 最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。
  • 为什么不按长度分呢，按长度也能得到正确答案，但是情况过多且之间的关系更复杂，所以 如何分是关键。 按起始位置分，分完之后的各种情况竟然可以递推。
  • 一个问题如果使用动规，我们要的值可能在最后一个角落，也就是说一直遍历到最后才能找到答案，答案是最后得到的值；也有可能是在遍历的过程中收集结果，最后的答案不一定是最后得到的值。
    • 如果答案是最后的值：那么使用递归求解 递归函数的语义就是问题本身
    • 如果答案不一定是最后的值： 那么递归函数的语义（或者dp数组的语义）就不是直接的问题本身，而是一些可能的情况，最后的答案是从这些可能的情况中按某种规则（题意）选择得到。这里的情况是什么最关键，也就是怎么分 。穷举所有情况->分类->加上最优性质->各个类别之间产生依赖关系（不独立）。 如果没有依赖关系可能就要换个分法了。情况可能有1-2种，这时是递归好想；也可能是n种，递归不好想。

一些常见的分类方法

针对不是递归的解法的dp，下面列举一些常见的分类方法。

  • 子数组
    • 一个子数组：列举开始位置或结束位置。[1-53最大子数组和](LeetCode 53 最大子数组和 - 动态规划解法.md) [14-978最长湍流子数组](LeetCode 978 最长湍流子数组.md)
    • 两个数组：列举两个开始位置或结束位置。[13-718最长重复子数组](LeetCode 718 最长重复子数组.md)

0-1背包问题

https://www.bilibili.com/video/BV16Y411v7Y6/?spm_id_from=333.788&vd_source=a9a24992f7f570a16d5a331e8fed9f0d

对于本层的输入是选还是不选是核心。

© 2026 我的博客