动态规划 – 常见普通题型及状态表示
坐标型 & 双序列型
序列型动态规划给你一个序列。坐标型一般给你一个 2D 数组，双序列型动态规划一般给你两个字符串 S、T。
这两种题目的状态表示本质上来说是一个二维表格。那么，状态表示一般为 dp[i][j]，表示位于这个表格的第 i 行第 j 列的答案。
这样的题目，LeetCode 里面还是不少的，先列举一些上来就给你 2D 数组的：
都是给你一个 2D 棋盘，然后你可以在上面按照某种规则走动，最后要求最值或者符合要求的方案数量。状态标识 dp[i][j] 就是坐标 (i, j) 的答案，允许走动的规则就是状态转移的规则。
LeetCode 62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明: m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右示例 2:
输入: m = 7, n = 3
输出: 28可以很容易看出，每个格子可以由它上面的格子和左边的格子转移过来，因此，状态转移方程为：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。
class Solution {
public:
int uniquePaths(int m, int n) {
int dp[m + 1][n + 1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= m; i ++) {
for (int j = 1; j <= n; j ++) {
if (i == 1 && j == 1) dp[i][j] = 1;
else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m][n];
}
};给你两个字符串的题目，经典的也有许多：
都是给你两个字符串，在这两个字符串上进行匹配的操作，dp[i][j] 表示匹配完了字符串 S[1...i]、T[1...j] 的答案，状态转移一般就对应匹配操作。
LeetCode 1143. 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。示例 2:
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。示例 3:
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。提示:
1 <= text1.length <= 10001 <= text2.length <= 1000- 输入的字符串只含有小写英文字符。
状态表示:
dp[i][j] 表示字符串 text1[1...i] 与 text2[1...j] 的最长公共子序列。
状态转移:
$$ dp[i][j] = \left\{ \begin{matrix} dp[i - 1][j - 1] + 1, text1[i] == text2[j] \hfill \\ \max(dp[i - 1][j], dp[i][j - 1]), otherwise. \hfill \\ \end{matrix} \right. $$
使用样例字符串 "ace", "abcde" 推出的动态规划状态表格为：
| a | b | c | d | e | |
|---|---|---|---|---|---|
| a | 1 | 1 | 1 | 1 | 1 |
| c | 1 | 1 | 2 | 2 | 2 |
| e | 1 | 1 | 2 | 2 | 3 |
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.length(), n = text2.length();
int dp[m + 1][n + 1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= m; i ++) {
for (int j = 1; j <= n; j ++) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
};划分型动态规划
划分型动态规划的特点就是给你一个序列，你要把它不重不漏的划分成 K 个区间。这种问题一个很直接的思路就是 dp[i] 表示考虑了序列前 i 个元素。
这样的题目在 LeetCode 里面也很经典：
考虑这类问题的转移，我们通常先枚举一个状态 dp[i]，然后考虑将序列 [i + 1, j] 接在后面自成一段，进而转移到状态 dp[j]。
如果严格分成 K 段，那么应该增加一维 [k] 表示当前分成了几段。本题型重要的还是：将序列 [i + 1, j] 接在后面自成一段这种状态转移的思想。
LeetCode 132. 分割回文串 II
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的最少分割次数。
示例:
输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。状态表示:
dp[i] 表示将 s[1...i] 拆成回文串最少需要拆几段。
状态转移:
$dp[i] = \min(dp[j]) + 1, j < i\ and \ s[j + 1 \cdots i]\ is\ palindrome.$
class Solution {
public:
bool check(int x, int y, string s){
for (int i = x; i <= y; i++){
if (s[i - 1] != s[x + y - i - 1]) return false;
}
return true;
}
int minCut(string s) {
int n = s.length();
int dp[n + 1];
memset(dp, -1, sizeof(dp));
dp[0] = 0;
for (int i = 1; i <= n; i ++){
for (int j = 0; j < i; j ++){
if (dp[j] == -1 || !check(j + 1, i, s)) continue;
if (dp[i] == -1 || dp[i] > dp[j] + 1) dp[i] = dp[j] + 1;
}
}
return dp[n] - 1;
}
};状态压缩动态规划
我们暂时只讨论比较简单的状态压缩动态规划，先不讨论基于连通性状态压缩的动态规划。
状态压缩动态规划的特点就是使用一个数的二进制形式保存状态，比如，0，1，2，3 四把椅子有没有人座，我们可以使用 [0/1][0/1][0/1][0/1] 来表示，也可以使用 [0...7] 来表示。
那么引入了二进制来表示状态之后，写代码就方便了许多。想想看，你的状态中有这么多维都需要分别写代码处理是不是很头疼呢。
这里，普及一些位运算常用写法，假设 bits 为状态压缩的数：
- 判断第 j 位是否为 1:
(bits >> j) & 1 - 将第 j 位变成 1:
bits | (1 << j) - 将第 j 位变成 0:
bits & ~(1 << j)
额外说一点，其实需要状态压缩的题目非常好分辨，你看数据范围的某一维度非常小，那么十有八九是留给你状态压缩用的。
LeetCode 1349. 参加考试的最大学生数
给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的（不可用），就用 '#' 表示；否则，用 '.' 表示。
学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷，但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的一起参加考试且无法作弊的最大学生人数。
学生必须坐在状况良好的座位上。
示例 1:
输入：seats = [["#",".","#","#",".","#"],
[".","#","#","#","#","."],
["#",".","#","#",".","#"]]
输出：4
解释：教师可以让 4 个学生坐在可用的座位上，这样他们就无法在考试中作弊。 示例 2:
输入：seats = [[".","#"],
["#","#"],
["#","."],
["#","#"],
[".","#"]]
输出：3
解释：让所有学生坐在可用的座位上。示例 3:
输入：seats = [["#",".",".",".","#"],
[".","#",".","#","."],
[".",".","#",".","."],
[".","#",".","#","."],
["#",".",".",".","#"]]
输出：10
解释：让学生坐在第 1、3 和 5 列的可用座位上。提示:
seats只包含字符'.'和'#'m == seats.lengthn == seats[i].length1 <= m <= 81 <= n <= 8
状态表示:
dp[i][bits] 表示第 i 行座位情况为 bits 时，前 i 行合法状态下最多坐多少人。（bits 中 0 表示没人坐，1 表示有人坐。）
状态转移:
$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行情况 $bits_{cur}$，第i - 1行情况 $bits_{pre}$，没有人可以作弊。- 若
i行第j个位置有人坐，那么i行j - 1、j + 1两个位置不能做坐人。 - 若
i行第j个位置有人坐，那么i - 1行j - 1、j + 1两个位置不能做坐人。
- 若
class Solution {
public:
int bcount(int x) {
unsigned int cnt = 0;
while (x) {
cnt ++;
x &= (x - 1);
}
return cnt;
}
int maxStudents(vector<vector<char>>& seats) {
int n = seats.size(), m = seats[0].size();
int dp[n + 1][1 << m];
memset(dp, -1, sizeof(dp));
dp[0][0] = 0;
int lim = (1 << m);
for (int i = 1; i <= n; i ++){
for (int cur = 0; cur < lim; cur ++){
for (int pre = 0; pre < lim; pre ++){
if (dp[i - 1][pre] == -1) continue; // 第 i - 1 行情况 pre 的方案不存在
bool flag = true;
for (int j = 0; j < m; j ++){
if (((cur >> j) & 1) == 0) continue; // 如果这个位置没人坐，不用检查了
if (seats[i - 1][j] == '#') flag = false; // 有人坐，但椅子坏了
if (j >= 1 && ((cur >> (j - 1)) & 1)) flag = false; // 有人坐，但左边有人
if (j + 1 < m && ((cur >> (j + 1)) & 1)) flag = false; // 有人坐，但右边有人
if (j >= 1 && ((pre >> (j - 1)) & 1)) flag = false; // 有人坐，但左前有人
if (j + 1 < m && ((pre >> (j + 1)) & 1)) flag = false; // 有人坐，但右前有人
}
if (flag == false) continue;
dp[i][cur] = max(dp[i][cur], dp[i - 1][pre] + bcount(cur));
}
}
}
int ans = 0;
for (int s = 0; s < lim; s ++) {
ans = max(ans, dp[n][s]);
}
return ans;
}
};总结
坐标型、双序列型动态规划
状态本质为二维表格，用 dp[i][j] 表示在表格 i 行 j 列的答案。
划分型动态规划
将序列不重不漏分成若干份，转移的时候考虑将 [i + 1, j] 接在状态 dp[i] 后，形成状态 dp[j]。
状态压缩动态规划
使用二进制 01 串来表示状态，表示维度通常不大。
