Skip to main content

Dynamic Programming

David LiuNovember 22, 2024About 16 min

Dynamic Programming

动态规划，避免重复计算

动态规划的题必须是求最优值/可行性/方案数这三种情况之一

动态规划的状态依赖必须有方向性，不可以有循环依赖

坐标型动态规划的状态：坐标

坐标型动态规划的方程：上一步坐标

动态规划/自底向上 vs 记忆化搜索/备忘录法/自顶向下

  • 动态规划优点：写起来简短且部分问题经过滚动数组优化以后可以节省空间
  • 备忘录法优点：部分问题可以剪枝避免不必要计算（不过大部分问题不需要剪枝）

eg. lc397. 整数替换

目标

  • 最优值/最值
    • 最优子结构
    • 可以结合第二个状态转移方程，同步计算，来保证最值的唯一性（比如
      • 最大值和最小值各一个状态转移方程
      • 持有一张股票和不持有股票各一个状态转移方程
  • 方案数/计数
    • 方案总数
    • 概率期望
    • 构造求和
  • 可行性/判别/存在

Eg. 背包类问题，可以这三种问题都有对应的题目

最优值

  • dp的值的类型是最优值的类型
  • dp[大问题]=max
  • dp[大问题]=min

方案数

  • dpl的值的类型是方案数（整数）
  • dp[大问题]=sum

可行性

  • dp的值是true/false
  • dp[大问题]=or

代码通常用 for 小问题 if dp[小问题]==true then break 的形式实现

不用dp的场景

  • 找具体方案 99%

    （最优方案还行，全部方案不太可能，和dfs枚举差不多）

  • 输入数据无序，除背包外，60%

  • 暴力算法已经是多项式时间复杂度，80%

组成部分

状态、转移、边界、（顺序

  • 状态
  • 转移
  • 边界
  • 顺序
  • 答案

状态 State

确定状态

研究最优策略的最后一步，化为子问题

  • 基本状态
    • 坐标
    • 序列
    • 区间
    • 状压
    • 树型
    • 数位
  • 约束状态
    • 状态
    • 背包

转移 Transition

转移方程

根据子问题定义直接得到

  • 填表法：从已知往当前填 Tabulation

    大部分情况如此，比较直观，就是状态转移方程

  • 刷表法：从当前往未知刷

    适合于部分边只有单向的情况

边界 Base

初始条件和边界情况

细心，考虑周全

顺序 Sequence

计算顺序

  1. 遍历过程中，所需的状态必须是已经计算出来的。
  2. 遍历结束后，存储结果的那个位置必须已经被计算出来。

例如

  1. 滚动数组的时候，考虑利用之前的计算结果；用了滚动数组之后，01背包的第二维度倒着，完全背包正着
  2. 区间dp的时候，
    • i从末尾开始，j从j+1往后；
    • 或者j从1，i从0-i这样枚举
    • 或者先枚举len，再固定窗口i++，j++

答案

  • 答案就是最后的状态，比如f[n]

  • 答案是f中的满足条件的值

    例如：f中的最大值，f中的最小值，eg 坐标型，有的时候求最大/小值

  • 答案是利用f计算出来的值

    例如：

要素

  • 状态：根据题目类型来设计

  • 转移/方程

  • 边界

    • 起点在哪
    • 第0行第0列

  • 顺序

  • 答案：终点在哪

确定状态

  • 研究最优策略的最后一步
  • 化为子问题

转移方程

  • 根据子问题定义直接得到

初始条件和边界情况

  • 细心，考虑周全

计算顺序

  • 利用之前的计算结果

解题步骤

  1. 判断是否DP
  2. 判断哪种DP
  3. 要素设计

关键词

  • 路径一坐标

  • 子序列一坐标

  • 和（余数）一背包

状态

动态规划需要开一个状态数组，数组的每个元素或者f[i]或者f[i][j]代表什么

特殊情况下会有多个状态和多个状态转移方程

确定状态需要两个意识：

  • 最后一步，最后一步有哪些方案，如何转移

    • 定义的状态知道最后一步是什么

      根据条件，直接转移，eg. 打家劫舍，爬楼梯等

    • 不然就需要通过额外一重循环来遍历选择空间（一个状态限制选择空间）

      • 区间型，找断点，枚举k in [i,j]之间从k处断开
      • 接龙型，找上家，枚举j in [0,i]之间从j处接上
      • 划分型，找断点，枚举j in [0,i]之间从j处分开

  • 子问题

最后一步

以石子游戏为例，

虽然我们不知最优策略是什么，但是最优策略肯定是K枚硬币a1,a2,,ak面值加起来是27

所以一定有一枚最后的硬币：ak

除掉这枚硬币，前面硬币的面值加起来是27-ak

  1. 关键点1

     我们不关心前面的K-1枚硬币是怎么拼出27-ak的（可能有1种拼法，可能有100种拼法)，而且我们现在甚至还不知道ak和K，但是我们确定前面的硬币拼出了27-ak

  2. 关键点2

     因为是最优策略，所以拼出27-ak的硬币数一定要最少，否则这就不是最优策略了

状态分类

可以抽象成DAG上的最短路、最长路问题

  1. 第一类状态：以当前结点为起点的性质（最优值、方案数、可行性）
  2. 第二类状态：以当前结点为终点的性质（最优值、方案数、可行性）

大多数情况下，使用如下：

  1. 递归写法，记忆化搜索，只能采用的第一类状态，因为他只能是自顶向下
  2. 迭代写法，动态规划，可以第一类、也可以第二类
    1. 第二类状态，最为常用，大多数问题都是采用这种
    2. 第一类状态，
      • 主要是从记忆化搜索翻译过来是采用
      • 或者是博弈问题，因为博弈问题只能从头到尾来算边不可逆，且终点不知

常见状态

基准

  • 坐标型

    dp[i]：到i的性质，本质上就是从起点到i结尾的一条路径就是子序列

    • 子序型

      dp[i]：以i结尾的子序列

      • 子串型

        Kedane

  • 序列型

    • 前序型

      dp[i]：前i个元素的性质

    • 后序型

      dp[i]：从i开头到结尾的性质

    • 划分型

  • 区间型

  • 状压型

    排列类问题需要状压dp

    本质是各个位置的元素的离散状态压缩成一个2/n进制数

  • 数位型

  • 树上型

约束

  • 背包型

    dp[i][j]：前i个元素，费用总和为j

    多维费用：dp[i][j][k]

    eg. Coin change

  • 状态型/离散型

    为每个有意义状态编号（无效状态或非法状态无需编号，因为无效状态的值相当于0不会被考虑）

    各个状态可能有各自的转移方程（有的题目可能形式类似，可以统一在一起）

    eg.

    • 最大子数组积，dp[i][j]其中j为0/1表示最大值/最小值
    • 股票买卖，0/1表示末位是否持有股票
    • 粉刷房子I, II, III，dp[i][j]其中j表示末位(i-1)粉刷成什么颜色

转移

最值

  • dp的值的类型是最优值的类型
  • dp[大问题]=max
  • dp[大问题]=min

这类问题有时可以结合单点修改线段树进行优化

博弈型

由于换序，要取反

dp[i]=max{k-dp[i-1]};

计数

方案数

  • dp的值的类型是方案数
  • dp[大问题]=sum

组合数

dp[大问题]=sum

卡特兰数：f[n]=sum{f[i]f[n-1-i]}

概率型

判别

可行性

  • dp的值是true/false
  • dp[大问题]=or
  • 代码通常用 for 小问题 if dp[小问题]==true then break 的形式实现

类型

动态规划的题型分类有什么用？

不同题型的动态规划的状态表示方法是不同的
如果成功的找对了题型，就能够解决DP最难的状态表示问题

状态定义类

  1. 坐标型动态规划(20%)

f[i]表示以i结尾的序列性质

  1. 一维

    状态：dp[i]表示从起点到坐标i的最优值/方案数/可行性

  2. 二维

    状态：dp[i][j]表示从起点到坐标i,j的最优值/方案数/可行性

    代表题：Triangle, Unique Paths

  3. 子序型/接龙型(5%)

    状态：dp[i]表示以坐标i结尾的子序列的最优值/方案数/可行性

    • 最长
    • 个数

    题目通常会给你个接龙规则：问你最长的龙有多长

    状态：dp[i]表示以坐标为i的元素结尾的最长龙的长度

    方程通常是：dp[i]=max{dp[j]]+1|ok(j,i)}, j的后面可以接上i

    • 子串型

      要求连续

      Kadane 算法

  4. 序列型/前缀型动态规划(20%)

    状态：f[i]表示前i个元素a[0],a[1],...,a[i-1]的某种性质

    • 划分型动态规划(20%)

      • 无限划分：dp[i]表示前i个字符的最优值/方案数/可行性
      • 有限划分：dp[i][j]表示前i个字符划分为j个部分的最优值/方案数/可行性

      代表题：Word Break, Word Break Ill

    • 背包型动态规划(10%)

      dp[i][j]表示前ⅰ个物品里选出物品组成和为j的大小的最优值/方案数/可行性

      代表题：Backpack 系列

    • 匹配型/双序型

      dp[i][j]表示第1个字符串的前i个学符匹配上第2个字符串的前j个字符的最优值/方案数/可行性

      代表题：Longest Common Subsequence, Wildcard Matching

  5. 区间型动态规划(15%)

    dp[i][j]表示区间[i,j]的最优值/方案数/可行性

    dp[i][len]表示i为首len长度的性质

    代表题：Stone Game, Burst Balloons, isPalindrome

  6. 状态型

    状态机，会有多个状态转移方程

    代表题：乘积最大子序列，股票买卖

  7. 状压型动态规划

    TSP

  8. 树上型动态规划

转移方程类

  1. 博弈型动态规划(5%)

    可以结合各类定义：前序型/后序型、区间型、

  2. 综合型动态规划(5%)

  3. 概率型动态规划

    求概率期望

  1. 坐标型动态规划(20%)

    • 子序列型动态规划(5%)
      • 最长
      • 个数
      • 子串型

  2. 序列型动态规划(20%)

    1. 划分型
    2. 背包型
    3. 匹配型

  3. 前缀型动态规划

    • 划分型动态规划(20%)
    • 匹配型/双序型
    • 背包型动态规划(10%)

  4. 区间型动态规划(15%)

  5. 博弈型动态规划(5%)

  6. 综合型动态规划(5%)

  7. 概率型动态规划

  8. 状压型动态规划

    TSP

  9. 树型动态规划

优化

  • 空间：滚动数组优化

    一般的：多开一个位置，然后%，可以减少rotate的时间，时间空间优化很大

    如果仅以来于上一层，可以滚动数组都无需开，但是需要注意顺序：

    • 倒序更新，如01背包问题、三角形路径问题

    如果依赖本层和上一层，可以滚动数组都无需开，但是需要注意顺序：

    • 正序更新，如完全背包问题、矩阵路径问题

  • 时间

    • 斜率优化
    • 四边形优化
    • 线段树优化（单点修改、区间最值）

动态规划的题目分为两大类，

它们都存在一定的递推性质。

  • 一种是求最优解类，典型问题是背包问题，

    递推性质叫做 「最优子结构」 ——即当前问题的最优解取决于子问题的最优解，

  • 另一种就是计数类，比如这里的统计方案数的问题，

    当前问题的方案数取决于子问题的方案数。

特征

  • 最优子结构

    最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面状态推导出来。

    注意要确保我们考察了最优解中用到的所有子问题。

    1. 证明问题最优解的第一个组成部分是做出一个选择；
    2. 对于一个给定问题，在其可能的第一步选择中，假定你已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择；
    3. 给定可获得的最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间；
    4. 证明作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。方法是反证法，考虑加入某个子问题的解不是其自身的最优解，那么就可以从原问题的解中用该子问题的最优解替换掉当前的非最优解，从而得到原问题的一个更优的解，从而与原问题最优解的假设矛盾。

    方面：

    1. 原问题的最优解中涉及多少个子问题；
    2. 确定最优解使用哪些子问题时，需要考察多少种选择。

  • 无后效性

    已经求解的子问题，不会再受到后续决策的影响。

    • 在推导后面阶段状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步步推导出来的。
    • 某阶段状态一旦确定，就不受之后阶段的决策影响。

    无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。

  • 重复子问题

    如果有大量的重叠子问题，我们可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率。

常见术语

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

子数组/子串：连续

计数和最优DP

可以发现，计数 DP 和最优化 DP 都是在一个范围 mega 内求一个值（大小值、最优值），这个值通过将 mega 中的所有元素做一次处理，再对处理值做一次整合得到。

例如，对于 0-1 背包问题，mega 中的元素为背包内的所有物品组成的集合，对于 mega 中的一个方案 S，我们对 S 做一次处理，处理得到的结果 w(S) 为 S 中物品的总价值，对所有得到的处理值，我们取最大值，得到问题的答案。

对于计数问题，mega 中的元素为要计算元素个数的集合 S，它的处理是把所有的 S 中元素变为 1，然后将这些 1 通过加法的方式汇总起来，因为每一个 S 中元素都对应一个 1，所以这样得到的值就是 S 中元素个数。

当汇总操作为最大/最小值时，我们可以将 mega 分成任意若干个部分，只需这些部分的并为 mega 即可，无需无交的条件。而计数问题由于不满足这个条件，所以我们需要将 mega 分成若干个部分，这些部分两两无交，这就是与最优化 DP 的区别。

理论

多阶段决策

回溯法中，每次决策对应于给一个结点产生新的子树，而解的生成过程对应一颗解答树，结点的层数就是“下一个待填充位置”cur

隐式图：有些问题的图不是事先给的，而是程序动态生成的

eg. 路径寻找问题，可以归结为隐式图的遍历

隐式图搜索、产生式系统

多阶段决策问题：每做一次决策就可以得到解的一部分，当所有决策做完之后，完整的解就浮出水面了（之前在回溯法中提过）

多段图：特殊的DAG，其结点可以划分为若干个阶段，每个阶段只由上一个阶段所决定。

单向TSP：阶段是列，每一列是一个阶段，每个阶段三种决策：直行右上、右下

0-1背包问题

完全背包问题：带权DAG（等于硬币兑换）

可以滚动数组第一维度

阶段定义了天然的计算顺序

DAG是DP的基础，很多问题都可以转化为DAG上的最长路、最短路或路径计数问题。

二元关系可以用图来建模。

嵌套矩阵问题：可嵌套可以用有向边

DAG最长/短路有两种“对称”的状态定义方式：

  1. f[i]为从i出发的最长路，则f[i]=max{f[j]+1|(i,j)in E}
  2. f[i]为以i结束的最短路，则f[i]=max{f[j]+1|(j,i)in E}

主要是用状态2，状态1比较麻烦，有的时候会有一些坑，不推荐使用

使用状态2时，有时还会遇到一个问题：状态转移方程可能可能不好计算，因为很多时候可以很方便枚举从i出发的所有边(i,j)，却不方便反着枚举(j,i)。特别是在有些题目中，这些边有明显的实际背景，对应的过程不可逆。

这时候需要用“刷表法”

“填表法”：对于每个状态i，找到f[i]依赖的所有状态

“刷表法”：对于每个状态i，更新f[i]影响的所有状态

对应到DAG中，相当于按照拓扑排序枚举i，对于i枚举出边，更新j

  • 记忆化搜索的备忘录往往是状态1的定义方式，因为自底向上
  • 迭代的写法，一般采用状态2
David's Blog
Copyright © 2025 David Liu