Typescript-Algorithms
    Preparing search index...

    掌握动态规划（DP）是没有捷径的，咱们唯一能做的，就是投入时间猛猛刷题。好比学数学，只看书看视频而不做习题，是不能说学会的。

    我能做的，是帮你节省找题的时间，并把这些题分类整理好。有着相同套路的题，一起做效率会更高，也更能领悟到 DP 的精髓。所以推荐按照专题刷。

    题目已按照难度分排序（右侧数字为难度分）。如果遇到难度很大，题解都看不懂的题目，建议直接跳过，二刷的时候再来尝试。

    动态规划算法题DP题单动态规划题单入门动态规划题目动态规划新手教程力扣DP力扣动态规划leetcode动态规划leetcode dp 灵茶山艾府 灵神 灵神题单

    记忆化搜索是新手村神器（甚至可以用到游戏后期），推荐先看 动态规划入门：从记忆化搜索到递推。

    但记忆化搜索并不是万能的，某些题目只有写成递推，才能结合数据结构等来优化时间复杂度，多数题目还可以优化空间复杂度。所以尽量在写完记忆化搜索后，把递推的代码也写一下。熟练之后直接写递推也可以。

    讲解

    问：在 1:1 翻译的过程中，如何根据记忆化搜索，确定递推数组（DP 数组）的大小？为什么有时候要开 n+1 大小的数组，有时候要开 n+2 大小的数组？

    答：看记忆化搜索的参数的范围（最小值和最大值）。例如 i 最小是 −1（递归边界也算），最大是 n−1（递归入口），那么一共有 n+1 个不同的 i，就需要开 n+1 大小的 DP 数组。如果 i 最小是 −2，最大是 n−1，一共有 n+2 个不同的 i，就需要开 n+2 大小的 DP 数组。

    思维扩展：

    有两种做法：

    1. 定义状态 f[i] 表示以 a[i] 结尾的最大子数组和，不和 i 左边拼起来就是 f[i]=a[i]，和 i 左边拼起来就是 f[i]=f[i−1]+a[i]，取最大值就得到了状态转移方程 f[i]=max(f[i−1],0)+a[i]，答案为 max(f)。这个做法也叫做 Kadane 算法。
    2. 用 前缀和，转化成 121. 买卖股票的最佳时机。

    思维扩展：

    完成本章后，请思考：什么时候要返回 f[n]，什么时候要返回 max(f)？

    对于一些二维 DP（例如背包、最长公共子序列），如果把 DP 矩阵画出来，其实状态转移可以视作在网格图上的移动。所以在学习相对更抽象的二维 DP 之前，做一些形象的网格图 DP 会让后续的学习更轻松（比如 0-1 背包的空间优化写法为什么要倒序遍历）。

    讲解

    思维扩展：

    讲解：0-1 背包 完全背包【基础算法精讲 18】

    每个物品只能选一次。

    进阶：

    物品可以重复选，无个数限制。

    问：关于完全背包，有两种写法，一种是外层循环枚举物品，内层循环枚举体积；另一种是外层循环枚举体积，内层循环枚举物品。如何评价这两种写法的优劣？

    答：两种写法都可以，但更推荐前者。外层循环枚举物品的写法，只会遍历物品数组一次；而内层循环枚举物品的写法，会遍历物品数组多次。从 cache 的角度分析，多次遍历数组会导致额外的 cache miss，带来额外的开销。所以虽然这两种写法的时间空间复杂度是一样的，但外层循环枚举物品的写法常数更小。

    物品可以重复选，有个数限制。

    求方案数

    二进制优化

    同一组内的物品至多/恰好选一个。

    也叫树上背包、依赖背包等。

    注：目前力扣只有无依赖的背包，时间复杂度为 O(nW2)。如果有依赖，可以优化到 O(nW)。

    讲解：最长公共子序列 编辑距离【基础算法精讲 19】

    一般定义 f[i][j] 表示对 (s[:i],t[:j]) 的求解结果。

    思维扩展：

    思考题：

    115 题的扩展。给定字符串 s 和 t，你可以在 s 的任意位置插入一个字母，插入后，s 最多有多少个子序列等于 t？

    思路和代码见 评论。

    讲解：最长递增子序列【基础算法精讲 20】

    做法有很多：

    1. 枚举选哪个。（见讲解）
    2. 二分。（见讲解）
    3. 计算 a 和把 a 排序后的数组 sortedA 的最长公共子序列。（用 LCS 求 LIS）
    4. 数据结构优化。（见 2407 题）

    思维扩展：

    思考题：

    给定整数 k，构造一个数组 a，使得 a 恰好有 k 个最长递增子序列。

    解答（评论）

    一般定义 f[i] 表示长为 i 的前缀 a[:i] 能否划分。

    枚举最后一个子数组的左端点 L，从 f[L] 转移到 f[i]，并考虑 a[L:i] 是否满足要求。

    计算最少（最多）可以划分出多少段、最优划分得分等。

    一般定义 f[i] 表示长为 i 的前缀 a[:i] 在题目约束下，分割出的最少（最多）子数组个数（或者定义成分割方案数）。

    枚举最后一个子数组的左端点 L，从 f[L] 转移到 f[i]，并考虑 a[L:i] 对最优解的影响。

    将数组分成（恰好/至多）k 个连续子数组，计算与这些子数组有关的最优值。

    一般定义 f[i][j] 表示将长为 j 的前缀 a[:j] 分成 i 个连续子数组所得到的最优解。

    枚举最后一个子数组的左端点 L，从 f[i−1][L] 转移到 f[i][j]，并考虑 a[L:j] 对最优解的影响。

    注：对于恰好型划分 DP，可以通过控制内层循环的上下界，把时间复杂度从 O(nk) 优化至 O((n−k)k)。例如 3473 题。

    一般定义 f[i][j] 表示前缀 a[:i] 在状态 j 下的最优值。j 一般很小。

    讲解【基础算法精讲 21】

    发生在前缀/后缀之间的转移，例如从 f[i−1] 转移到 f[i]，或者从 f[j] 转移到 f[i]。

    思维扩展：

    计算合法子序列的最长长度、个数、元素和等。

    一般定义 f[x] 表示以元素 x 结尾的合法子序列的最长长度/个数/元素和，从子序列的倒数第二个数转移过来。

    注意这里的 x 不是下标，是元素值。如果 x 不是整数，或者值域范围很大，可以用哈希表代替数组。

    思维扩展：

    思维扩展：

    讲解：区间 DP【基础算法精讲 22】

    从数组的左右两端不断缩短，求解关于某段下标区间的最优值。

    一般定义 f[i][j] 表示下标区间 [i,j] 的最优值。

    对于类似合法括号字符串（RBS）的消除问题，通常根据题意，会有如下性质：

    1. 可以消除相邻的匹配字符。
    2. 相邻匹配字符消除后，原本不相邻的字符会变成相邻，可以继续消除。换句话说，设子串 A=x+B+y，如果 x 和 y 是匹配的（可以消除），且子串 B 可以完全消除，那么子串 A 可以完全消除。
    3. 设子串 A=B+C，如果子串 B 和 C 可以完全消除，那么子串 A 可以完全消除。

    满足上述性质的题目（例如 3563 题），可以用区间 DP 解决。

    定义 f(i,j) 表示消除 s[i] 到 s[j] 的最优值。

    • 根据性质 2，可以把 f(i,j) 缩小成子问题 f(i+1,j−1)。
    • 根据性质 3，可以枚举子串 B 的右端点，即枚举 k=i+1,i+3,i+5,…,j−2，把 f(i,j) 划分成子问题 f(i,k) 和 f(k+1,j)。注意这里枚举 k 的步长是 2，因为每次消除 2 个字符，被消除的子串长度一定是偶数。

    边界：f(i+1,i)，即空串。

    答案：f(0,n−1)。

    学习指南：

    暴力做法是枚举所有排列，对每个排列计算和题目有关的值，时间复杂度（通常来说）是 O(n!)。可以解决 n≤10 的问题。

    状压 DP 可以把时间复杂度（通常来说）优化至 O(n⋅2n)。可以解决 n≤20 的问题。

    一般有两种定义方式：

    1. 定义 f[S] 表示已经排列好的元素（下标）集合为 S 时，和题目有关的最优值。通过枚举当前位置要填的元素（下标）来转移。
    2. 定义 f[S] 表示可以选的元素（下标）集合为 S 时，和题目有关的最优值。通过枚举当前位置要填的元素（下标）来转移。

    注：部分题目由于暴搜+剪枝也能过，难度分仅供参考。

    一般定义 f[S][i] 表示未选（或者已选）的集合为 S，且上一个填的元素（下标）为 i 时，和题目有关的最优值。通过枚举当前位置要填的元素（下标）来转移。

    时间复杂度（通常来说）是 O(n2⋅2n)。

    讲解：从全排列到状压 DP

    本质上就是排列型 ②。

    相似问题：

    一般定义 f[S] 表示未选（或者已选）的集合为 S 时，和题目有关的最优值。通过枚举 S（或者 S 的补集 ∁U​S）的子集来转移。

    时间复杂度（通常来说）是 O(3n)，证明：

    对于大小为 n 的集合，它的大小为 m 的子集有 (mn​) 个，每个子集又有 2m 个子集。根据二项式定理，m=0∑n​(mn​)2m=(2+1)n=3n，所以「枚举子集的子集」的总体时间复杂度为 O(3n)。

    值得注意的是，枚举子集的子集还可以用「选或不选」来做，对于存在无效状态的情况，可以做到更优的时间复杂度。具体见 1349 题解 最后的写法。

    数位 DP v1.0 模板讲解

    数位 DP v2.0 模板讲解 上下界数位 DP

    下面是数位 DP v2.1 模板。相比 v2.0，不需要写 isNum 参数。

    注：只有上界约束的题目，相当于 low=0 或者 low=1。

    Python3

    Java

    C++

    Go

    # 代码示例：返回 [low, high] 中的恰好包含 target 个 0 的数字个数
# 比如 digitDP(0, 10, 1) == 2
# 要点：我们统计的是 0 的个数，需要区分【前导零】和【数字中的零】，前导零不能计入，而数字中的零需要计入
def digitDP(low: int, high: int, target: int) -> int:
    low_s = list(map(int, str(low)))  # 避免在 dfs 中频繁调用 int()
    high_s = list(map(int, str(high)))
    n = len(high_s)
    diff_lh = n - len(low_s)

    @cache
    def dfs(i: int, cnt0: int, limit_low: bool, limit_high: bool) -> int:
        if cnt0 > target:
            return 0  # 不合法
        if i == n:
            return 1 if cnt0 == target else 0

        lo = low_s[i - diff_lh] if limit_low and i >= diff_lh else 0
        hi = high_s[i] if limit_high else 9

        res = 0
        d = lo
        # 通过 limit_low 和 i 可以判断能否不填数字，无需 is_num 参数
        # 如果前导零不影响答案，去掉这个 if block
        if limit_low and i < diff_lh:
            # 不填数字，上界不受约束
            res = dfs(i + 1, cnt0, True, False)
            d = 1
        for d in range(d, hi + 1):
            res += dfs(i + 1,
                       cnt0 + (1 if d == 0 else 0),  # 统计 0 的个数
                       limit_low and d == lo,
                       limit_high and d == hi)

        # res %= MOD
        return res

    return dfs(0, 0, True, True)

    思维扩展：

    前置题单：单调栈（矩形系列/字典序最小/贡献法）

    一般用来维护一段转移来源的最值。

    1. 前提：区间右端点变大时，左端点也在变大（同滑动窗口）。
    2. 转移前，去掉队首无用数据。
    3. 计算转移（直接从队首转移）。
    4. 把数据（一般是 f[i]）插入队尾前，去掉队尾无用数据。

    讲解

    也叫凸包优化/凸壳优化（CHT，Convex Hull Trick）。

    把最多选 k 个物品的问题（时间复杂度高）转换成选任意个物品的问题（时间复杂度低）。

    注：可能有同学觉得树形 DP 没有重复访问同一个状态（重叠子问题），并不能算作 DP，而是算作普通的递归。这么说也有一定道理，不过考虑到思维方式和 DP 是一样的自底向上，所以仍然叫做树形 DP。此外，如果是自顶向下的递归做法，是存在重叠子问题的，一般要结合记忆化搜索实现。

    讲解：树形 DP：树的直径【基础算法精讲 23】

    注：求直径也有两次 DFS 的做法。

    讲解：树形 DP：打家劫舍 III【基础算法精讲 24】

    讲解：树形 DP：监控二叉树【基础算法精讲 25】，包含 968 的变形题。

    也叫二次扫描法。

    【图解】一张图秒懂换根 DP！

    注：前后缀分解，可以视作一条链上的换根 DP。

    另见【题单】图论算法 中的「全源最短路：Floyd」，本质是多维 DP。

    注意这些题目和回溯的区别，某些回溯题目要求输出所有方案，这里只要求输出一个。

    讲解

    部分题目也可以用状态机 DP 解决。

    如果涉及到的只是若干元素，而不是前缀/后缀这样的一段元素。也可以用「枚举右，维护左」思考，详见数据结构题单。

    补充题目：

    • 输入一个长为 n 的 prices 数组，你需要返回一个长为 n 的 answer 数组，其中 answer[i] 表示删除 prices[i]，也就是禁止在第 i 天买卖股票，在此约束下 121. 买卖股票的最佳时机 的答案。

    部分题目也可以用 BFS 解决。

    另见 图论题单 中的 Dijkstra 算法，例如：

    如何科学刷题？

    1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
    2. 二分查找（二分答案/最小化最大值/最大化最小值/第K小）
    3. 单调栈（基础/矩形面积/贡献法/最小字典序）
    4. 网格图（DFS/BFS/综合应用）
    5. 位运算（基础/性质/拆位/试填/恒等式/思维）
    6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
    7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
    8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
    9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
    10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
    11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
    12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

    我的题解精选（已分类）

    欢迎关注 B站@灵茶山艾府

    如果你发现有题目可以补充进来，欢迎评论反馈。

    Settings

    Member Visibility

    On This Page

    前言一、入门 DP二、网格图 DP三、背包四、经典线性 DP五、划分型 DP六、状态机 DP七、其他线性 DP八、区间 DP九、状态压缩 DP（状压 DP）十、数位 DP十一、优化 DP十二、树形 DP十三、图 DP十四、博弈 DP十五、概率/期望 DP专题：输出具体方案（打印方案）专题：前后缀分解专题：把 X 变成 Y专题：跳跃游戏其他算法题单