动态规划 – 常见普通题型及状态表示

正文索引 [隐藏]

上一节我们讲了序列型动态规划,一点精髓就是动态规划最重要的是状态间的顺序(阶段划分)。这个顺序可能是题目给你的,也可能是需要自己转化出来的,确定了这个顺序之后,就可以类比序列型动态规划做了。可以说,熟练掌握了序列型动态规划,你就在代码层面和逻辑层面掌握了动态规划,其他所有题目都可以使用自己的智慧解答出来。

那么接下来,各位同学要做的就是多做题、多接触不同类型,积累寻找阶段划分、状态表示与状态转移的经验与感觉。那么,我想把一些比较普通的类型一次性全部讲了。

坐标型 & 双序列型

序列型动态规划给你一个序列,一倍的快乐。坐标型一般给你一个 2D 数组,双序列型动态规划一般给你两个字符串 $S, T$(不要问我为啥这里的序列是字符串,问就是题面太难编)。

这两种题目的状态表示本质上来说是一个二维表格,两倍的快乐!那么,状态表示一般为 $dp[i][j]$ 表示位于这个表格的第 $i$ 行第 $j$ 列的答案。,或者。

这样的题目,LeetCode 里面还是不少的,现列举一些上来就给你 2D 数组的:62. 不同路径63. 不同路径 II64. 最小路径和576. 出界的路径数931. 下降路径最小和1289. 下降路径最小和 II1301. 最大得分的路径数目
都是给你一个 2D 棋盘,然后你可以在上面按照某种规则走动,最后要求最值或者符合要求的方案数量。状态标识 $dp[i][j]$ 就是坐标 $(i, j)$ 的答案,允许走动的规则就是状态转移的规则。

LC 62. 不同路径

状态表示: $dp[i][j]$表示走到了第 $i$ 行第 $j$ 列的方案数
边界:$dp[1][1] = 1$
状态转移:$dp[i][j] = dp[i − 1][j] + dp[i][? − j]$

计算样例 3 行 7 列的方案数,动态规划的状态表格为:
LC 62 DP Table

给你两个字符串的题目,经典的也有许多:72. 编辑距离1092. 最短公共超序列1143. 最长公共子序列
都是给你两个字符串,在这两个字符串上进行匹配的操作,$dp[i][j]$ 表示匹配完了字符串 $S[1\cdots i], T[1\cdots j]$ 的答案,状态转移一般就对应匹配操作。

LC 1143. 最长公共子序列

状态表示: $dp[i][j]$ 表示串 $text1[1\cdots i]$ 与 $text2[1\cdots j]$ 的最长公共子序列
边界:$dp[0][0]=1$
状态转移:

dp[i][j]=
\begin{cases}
dp[i−1][j−1]+1, text1[i]=text2[j],\\
max⁡(dp[i−1][j],dp[i][j−1]),otherwise.
\end{cases}

使用样例字符串 ace, abcde 推出的动态规划状态表格为:
LC 1143 DP Table

划分型动态规划

划分型动态规划的特点就是给你一个序列,你要把它不重不漏的划分成 $K$ 个区间。这种问题一个很直接的思路就是 $dp[i]$ 表示考虑了序列前 $i$ 个元素。

这样的题目在 LeetCode 里面也很经典:132. 分割回文串 II410. 分割数组的最大值1278. 分割回文串 III1335. 工作计划的最低难度

考虑这类问题的转移,我们通场先枚举一个状态 $dp[i]$,然后考虑将序列 $[i + 1, j]$ 接在后面自成一段,转移到状态 $dp[j]$(主动转移)。想想看这里的被动转移是什么。

如果严格分成 $K$ 段,那么应该增加一维 $[k]$ 表示当前分成了几段。本题型重要的还是:将序列 $[i + 1, j]$ 接在后面自成一段这种状态转移的思想。

LC 132. 分割回文串 II

状态表示: $dp[i]$ 表示将 $?[1\cdots i]$ 拆分成回文串的最少拆几段。
边界:$dp[0]=0$
状态转移:$dp[i]=\min⁡ {dp[j]+1 },j<i~and~s[j+1\cdots i]~is~palindrome$

这道题目和上一讲序列型动态规划类似,那我们同样也可以列出这样一个动态规划状态转移的表:
132 DP Table

状态压缩动态规划

我们暂时只讨论比较简单的状态压缩动态规划,先不讨论基于连通性状态压缩的动态规划。

状态压缩动态规划的特点就是使用一个数的二进制形式保存状态,比如,$0,1,2,3$ 四把椅子有没有人座,我们可以使用 $[0/1][0/1][0/1][0/1]$ 来表示,也可以使用 $[0\cdots 7]$ 来表示。

状态压缩示例

那么引入了二进制来表示状态之后,写代码就方便了许多。想想看,你的状态中有这么多维都需要分别写代码处理是不是很头疼呢。

这里,普及一些位运算常用写法,假设 bits 为状态压缩的数:

  • 判断第 $j$ 位是否为 $1$: (bits>>j)&1
  • 将第 $j$ 位变成 $1$: bits|(1<<j)
  • 将第 $j$ 为变成 $0$:bits&~(1<<j)

额外说一点,其实需要状态压缩的题目非常好分辨,你看数据范围的某一维度非常小,那么十有八九是留给你状态压缩用的。

这种题目,LeetCode 里并不多,最新的一期周赛中又出现:1349. 参加考试的最大学生数

LC

状态表示: $dp[i][bits]$ 表示第 $i$ 行座位情况为 $bits$ 前 $i$ 合法状态下最多坐多少人。($bits$ 中 $0$ 表示没人坐;$1$ 表示有人坐)
边界:$dp[0][0]= 0$
状态转移:$dp[i][bits_{cur}]=max(dp[i][bits_{cur}],dp[i−1][bits_{pre}]+bitcount(bits_{cur}))$ 且 $i$ 行 $bits_{cur}$,$i-1$ 行 $bits_{pre}$ 合法:

  • 第 $i$ 行情况 $bits_{cur}$,没有人坐到坏的位置上
  • $i−1$ 行情况 $bits_{pre}$, $i$ 行情况 $bits_{cur}$,没有人可以作弊
    • 若 $i$ 行第 $j$ 个位置有人坐,那么 $i$ 行 $j-1, j+1$ 两个位置不能做坐人
    • 若 $i$ 行第 $j$ 个位置有人坐,那么 $i-1$ 行 $j-1, j+1$ 两个位置不能做坐人

因为上图箭头根部的 1,所以指向的四个位置都必须是 0。

1349 状态压缩

Take Home Message

坐标型、双序列型动态规划:状态本质为二维表格,用 $dp[i][j]$ 表示在表格 $i$ 行 $j$ 列的答案
划分型动态规划:将序列不重不漏分成若干份,转移的时候考虑将 $[i+1,j]$ 接在状态 $dp[i]$ 后,形成状态 $dp[j]$
状态压缩动态规划:使用二进制 01 串来表示状态,表示维度通常不大。

习题……上面的都是!