8. 动态规划

8.1. 矩阵连乘

矩阵连乘，通过调整加括号的方式，使得乘法元素次数最少。设矩阵链 \(A[0:n-1]\) ， \(A[i]\) 的维度为 \(p_i \times p_{i+1}\) 。 \(m[i][j]\) 是计算 \(A[i:j],\ 0 \leqslant i \leqslant j \leqslant n-1\) 所需的最少乘法次数。

递推关系：

$$ m[i][j] = \begin{cases} \mathrm{min} \{ m[i][k] + m[k+1][j] + p_i \times p_{k+1} \times p_{j+1} \},\ i \leqslant k < j & & i \ne j \\ 0 & & i = j \end{cases} $$

\(\color{darkgreen}{Code}\)

 1// s[i][j] 记录 A[i:j] 的划分点 k
 2void matrixChain(int* p, int n, int** m, int** s)
 3{
 4  for(int i = 0; i < n; ++i) m[i][i] = 0;
 5  for(int gap = 1; gap < n; ++gap)
 6  {
 7    for(int i = 0; i + gap < n; ++i)
 8    {
 9      int j = i + gap;
10      m[i][j] = m[i+1][j] + p[i] * p[i+1] * p[j+1]; // k = i
11      s[i][j] = i;
12      for(int k = i+1; k < j; ++k)
13      {
14        int cost = m[i][k] + m[k+1][j] + p[i] * p[k+1] * p[j+1];
15        if(cost < m[i][j])
16        {
17          m[i][j] = cost;
18          s[i][j] = k;
19        }
20      }
21    }
22  }
23}

8.2. 最长公共子序列

用 \(c[i][j]\) 记录序列 \(X[0:i-1]\) （前 \(i\) 个字符）和 \(Y[0:j-1]\) （前 \(j\) 个字符）的最长公共子序列的长度。

递推关系：

\[\begin{split}c[0][j] & = 0,\ 0 \leqslant j \leqslant n \\ c[i][0] & = 0,\ 0 \leqslant i \leqslant m\end{split}\]
$$ c[i][j] = \begin{cases} c[i-1][j-1] + 1 & & {i,j > 0;\ X[i-1] = Y[j-1]} \\ \mathrm{max}\{ c[i-1][j], c[i][j-1] \} & & {i,j > 0;\ X[i-1] \ne Y[j-1]} \end{cases} $$

\(\color{darkgreen}{Code}\)

 1void lcsLength(char* x, int m, char* y, int n, int** c)
 2{
 3  for(int i = 0; i <= m; ++i) c[i][0] = 0;
 4  for(int j = 0; j <= n; ++j) c[0][j] = 0;
 5  for(int i = 1; i <= m; ++i)
 6  {
 7    for(int j = 1; j <=n; ++j)
 8    {
 9      if(x[i-1] == y[j-1]) c[i][j] = c[i-1][j-1] + 1; // 注意：这里是比较 x[i-1] 和 y[j-1]，而不是 x[i] 和 y[j]
10      else c[i][j] = max(c[i-1][j], c[i][j-1]);
11    }
12  }
13}

 1/* 记录并构造公共子序列 */
 2
 3// 方法一
 4
 5void lcsLength(char* x, int m, char* y, int n, int** c, int** b)
 6{
 7  for(int i = 0; i <= m; ++i) c[i][0] = 0;
 8  for(int j = 0; j <= n; ++j) c[0][j] = 0;
 9  for(int i = 1; i <= m; ++i)
10  {
11    for(int j = 1; j <=n; ++j)
12    {
13      if(x[i-1] == y[j-1])
14      {
15        c[i][j] = c[i-1][j-1] + 1;
16        b[i][j] = 0;
17      }
18      else
19      {
20        if(c[i-1][j] > c[i][j-1])
21        {
22          c[i][j] = c[i-1][j];
23          b[i][j] = 1;
24        }
25        else
26        {
27          c[i][j] = c[i][j-1];
28          b[i][j] = 2;
29        }
30      }
31    }
32  }
33}
34
35void lcs(char* x, int m, int n, int** b)
36{
37  if(m == 0 || n == 0) return;
38  if(b[m][n] == 0)
39  {
40    lcs(x, m-1, n-1, b);
41    cout << x[m-1];
42  }
43  else if(b[m][n] == 1) lcs(x, m-1, n, b);
44  else lcs(x, m, n-1, b);
45}

 1// 方法二
 2string lcs(const string a, const string b)
 3{
 4  const int m = a.size();
 5  const int n = b.size();
 6  vector<vector<string>> dp(2, vector<string>(n+1, ""));
 7  for(int i = 1; i <= m; ++i)
 8  {
 9    for(int j = 1; j <= n; ++j)
10    {
11      if(a[i-1] == b[j-1]) dp[i&1][j] = dp[(i-1)&1][j-1] + a[i-1];
12      else dp[i&1][j] = dp[(i-1)&1][j].size() > dp[i&1][j-1].size()? dp[(i-1)&1][j]: dp[i&1][j-1];
13    }
14  }
15  string res = dp[m&1][n];
16  dp.clear();
17  dp.shrink_to_fit();
18  return res;
19}

相关题：最短编辑距离。

\[\begin{split}d[0][j] & = j,\ 0 \leqslant j \leqslant n \\ d[i][0] & = i,\ 0 \leqslant i \leqslant m\end{split}\]
$$ d[i][j] = \begin{cases} d[i-1][j-1] & & {i,j > 0;\ X[i-1] = Y[j-1]} \\ \mathrm{min} \{ d[i-1][j], d[i][j-1], d[i-1][j-1] \} + 1 & & {i,j > 0;\ X[i-1] \ne Y[j-1]} \end{cases} $$

8.3. 最长上升子序列

  • 方法一

    设 \(dp[i]\) 是以 \(a[i]\) 结尾的最长上升子序列的长度。

    递推关系：

    \[dp[i] = \mathrm{max}\{ 1, dp[j]+1\ |\ j < i\ \text{且}\ a[j] < a[i]\}.\]

\(\color{darkgreen}{Code}\)

 1/* O(n^2) in time.*/
 2int n;
 3int a[MAX_N];
 4
 5int dp[MAX_N];
 6
 7int solve()
 8{
 9  int res = 0;
10  for(int i = 0; i < n; ++i)
11  {
12    dp[i] = 1;
13    for(int j = 0; j < i; ++ j)
14    {
15      if(a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
16    }
17    res = max(res, dp[i]);
18  }
19  return res;
20}

  • 方法二

    设 \(dp[i]\) 是长度为 \(i+1\) 的上升子序列中末尾元素的最小值。

\(\color{darkgreen}{Code}\)

 1/* https://leetcode.com/problems/longest-increasing-subsequence/ */
 2/* O(nlogn) in time.*/
 3class Solution
 4{
 5public:
 6  int lengthOfLIS(vector<int>& nums)
 7  {
 8    if(nums.size()<=1) return nums.size();
 9    int inf = INT_MAX;
10    int len = nums.size();
11    int* dp = new int[len];
12    fill(dp, dp+len, inf);
13    for(int k = 0; k < len; ++k) *lower_bound(dp, dp+len, nums[k]) = nums[k];
14    int length = lower_bound(dp, dp+len, inf) - dp;
15    delete[] dp;
16    return length;
17  }
18};

8.4. 最大子段和

设 \(dp[i]\) 是以 \(a[i]\) 结尾的最大子段和。

递推关系：

\[dp[i] = \mathrm{max}\{ dp[i-1] + a[i], a[i] \},\ 1 \leqslant i < n.\]

\(\color{darkgreen}{Code}\)

 1int maxSum(int* a, int n)
 2{
 3  int dp = 0;
 4  int res = 0;
 5  for(int i = 0; i < n; ++i)
 6  {
 7    dp = max(dp + a[i], a[i]);
 8    res = max(res, dp);
 9  }
10  return res;
11}

8.5. 0-1背包问题

设 \(dp[i][j]\) 表示从 \(0\) 到 \(i-1\) 这前 \(i\) 个物品中选出总重量不超过 \(j\) 的物品时总价值的最大值。

递推关系：

$$ dp[0][j] = 0,\ 0 \leqslant j \leqslant W $$ $$ dp[i+1][j] = \begin{cases} dp[i][j] & & j < w[i] \\ \mathrm{max}\{ dp[i][j], dp[i][j-w[i]] + v[i] \} & & j \geqslant w[i] \end{cases} $$

\(\color{darkgreen}{Code}\)

 1int n, W;
 2int w[MAX_N], v[MAX_N];
 3int dp[MAX_N+1][MAX_W+1];
 4int solve()
 5{
 6  for(int i = 0; i < n; ++i)
 7  {
 8    for(int j = 0; j <= W; ++j)
 9    {
10      if(j < w[i]) dp[i+1][j] = dp[i][j];
11      else dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]] + v[i]);
12    }
13  }
14  return dp[n][W];
15}

 1// 由于计算 dp[i+1] 只需要用到 dp[i] 和 dp[i+1]，因此可以进一步降低空间复杂度
 2int dp[2][MAX_W+1];
 3int solve()
 4{
 5  for(int i = 1; i <= n; ++i)
 6  {
 7    for(int j = 0; j <= W; ++j)
 8    {
 9      if (j < w[i - 1]) dp[i & 1][j] = dp[(i - 1) & 1][j];
10      else dp[i & 1][j] = max(dp[(i - 1) & 1][j], dp[(i - 1) & 1][j - w[i - 1]] + v[i - 1]);
11    }
12  }
13  return dp[n & 1][W];
14}

8.6. 状态压缩动态规划

动态规划的状态有时候不容易表示出来，需要用一些编码技术，把状态用简单的方式表示出来（压缩）。 典型方式：当需要表示一个集合有哪些元素时，往往用一个整数表示，整数的二进制表示中的1表示对应位置的元素存在于集合中，0表示不存在。

[Poj 3254] Corn Fields

问题描述：一个 \(N \times N\) 的矩阵牧场，每个方格单元有两种状态：可放牧（1）和不可放牧（0）；在这块牧场放牛，要求两个相邻的方格不能同时放牛（不包括斜着的），即牛与牛不能挨着；问有多少种放牛方案（一头牛都不放也是一种方案）？

策略：用一个集合（状态压缩）维护所有不相邻的情况，在此基础上再去考虑哪些方格可放牧。 设 \(dp[i][j]\) 表示：在第 \(i\) 行状态为 \(j\ (0 \leq j \leq 2^m-1)\) 时， 前 \(i+1\) 行牧场方格总共的放牛方案数量。

递推关系：

$$ dp[i][j] = \begin{cases} 1 & & {i=0;\ \text{状态 j 可以放牧且牛不相邻}} \\ \sum_{j^{\prime}} dp[i-1][j^{\prime}] & & {i>0;\ \text{状态 j 可以放牧且牛不相邻}} \\ 0 & & {\text{状态 j 不可以放牧或牛相邻}} \end{cases} $$

\(\color{darkgreen}{Code}\)

 1const int N = 13;
 2const int M = 1 << N;
 3const int mod = 10000007;
 4int field[N][N]; // 方格能否放牧的标志
 5int row_nadj_state[M]; // 不相邻的行状态编码
 6int row_forbid_state[M]; // 不可放牧的位置编码
 7int dp[N][M];
 8
 9bool hasAdj(int s)
10{
11  return (s & (s<<1));
12}
13bool locForbid(int i, int j)
14{
15  return (row_forbid_state[i] & row_nadj_state[j]);
16}
17int solve()
18{
19  for(int i = 0; i < N; ++i)
20  {
21    for(int c = 0; c < N; ++c)
22    {
23      if(field[i][c] == 0) row_forbid_state[i] += 1 << c;
24    }
25  }
26  int k = 0; // 不相邻行状态的数量
27  for(int s = 0; s < M; ++s)
28  {
29    if(!hasAdj(s)) row_nadj_state[k++] = s;
30  }
31  for(int j = 0; j < k; ++j)
32  {
33    if(!locForbid(0, j)) dp[0][j] = 1; // 第1行初始化
34  }
35  for(int i = 1; i < N; ++i)
36  {
37    for(int j = 0; j < k; ++j)
38    {
39      if(locForbid(i, j)) continue;
40      for(int pre_j = 0; pre_j < k; ++pre_j)
41      {
42        if(locForbid(i-1, pre_j)) continue;
43        if(!(row_nadj_state[pre_j] & row_nadj_state[j]))
44        {
45          dp[i][j] += dp[i-1][pre_j]; // 上下两行牛不相邻
46          dp[i][j] = dp[i][j] % mod;
47        }
48      }
49    }
50  }
51  int res = 0;
52  for(int j = 0; j < k; ++j)
53  {
54    res += dp[N-1][j];
55    res = res % mod;
56  }
57  return res;
58}

[Poj 3311] Hie With The Pie

问题描述：一个送外卖的人，从起点0出发，要经过所有地点一次，然后再回到起点，求最少花费的代价（旅行商问题）。

策略：假设当前已经访问过的顶点集合为 \(S\) （起点0当做未访问过），当前所在顶点为 \(v\) ， \(dp[S][v]\) 表示：从 \(v\) 出发访问剩余所有顶点，最终回到起点0的路径的权重总和的最小值。设 \(V\) 表示所有顶点的集合。

递推关系：

\[\begin{split}dp[V][0] &= 0 \\ dp[S][v] &= \mathrm{min}\{ dp[S \cup u][u] + d[v][u] \},\ u \notin S\end{split}\]

\(\color{darkgreen}{Code}\)

 1// 递归：时间复杂度 O(n^2 \times 2^n)
 2int d[N][N]; // 邻接矩阵
 3int dp[1 << N][N];
 4
 5int minCost(int S, int v)
 6{
 7  if(dp[S][v] >= 0) return dp[S][v]; // 记忆化搜索已经有的结果
 8  if(S == (1<<N)-1 && v == 0) return dp[S][v] = 0; // 递归终止条件：已访问过所有顶点并返回起点0
 9  int res = INF;
10  for(int u = 0; u < N; ++u)
11  {
12    if(!(S >> u & 1)) // 顶点 u 未访问过，下一步移动到顶点 u
13    {
14      res = min(res, minCost(S | 1 << u, u) + d[v][u]);
15    }
16  }
17  return dp[S][v] = res;
18}
19int solve()
20{
21  memset(dp, -1, sizeof(dp));
22  return minCost(0, 0);
23}

 1// 循环
 2int d[N][N]; // 邻接矩阵
 3int dp[1 << N][N];
 4int solve()
 5{
 6  for(int S = 0; S < 1<<N; ++S) fill(dp[S], dp[S] + N, INF); // 用足够大的值初始化
 7  dp[(1<<N)-1][0] = 0; // 初始化
 8  for(int S = (1<<N)-2; S >= 0; --S)
 9  {
10    for(int v = 0; v < N; ++v) // 当 v 不属于集合 S，dp[S][v]是无效的、从 0 出发不可达的状态
11    {
12      for(int u = 0; u < N; ++u)
13      {
14        if(!(S >> u & 1)) dp[S][v] = min(dp[S][v], dp[S | 1<<u][u] + d[v][u]);
15      }
16    }
17  }
18  return dp[0][0];
19}

相反地，参考资料1将 \(dp[S][v]\) 定义为：走完集合 \(S\) 后最后停留在顶点 \(v\) 的最小代价。

8.7. 实例

  • 有面值 1,5,10,20,50,100 的人民币，求问 10000 有多少种组成方法？

    https://www.zhihu.com/question/315108379

    \(\color{darkgreen}{Code}\)

     1import numpy as np
 2money = np.array([1, 5, 10, 20, 50, 100])
 3dp = np.array([[0 for i in range(10000+1)] for j in range(6+1)], dtype=np.int64)
 4## dp[m,n]: first m currency values, make money n
 5dp[0,:] = 0
 6dp[:,0] = 1
 7for m in range(1,6+1):
 8    for n in range(1, 10000+1):
 9        if n >= money[m-1]:
10            dp[m,n] = dp[m,n-money[m-1]] + dp[m-1,n]
11        else:
12            dp[m,n] = dp[m-1,n]
13print dp[6, 10000]

     1// 作者：李泽政
 2// 链接：https://www.zhihu.com/question/315108379/answer/620254961
 3
 4#include<cstdio>
 5#define maxn 10001
 6long long dp[maxn];
 7int main(void)
 8{
 9    int i,j,num[] = {5, 10, 20, 50, 100};
10    // 把 1 从 num[] 中去掉了，转化到初始化中。全用 1 元只能得到一种组成方案
11    for(i = 0; i < maxn; ++i)
12        dp[i] = 1;
13    for(i = 0; i < 5; ++i)
14        for(j = num[i]; j < maxn; ++j)
15            dp[j] += dp[j - num[i]];
16    printf("%lld", dp[maxn - 1]);
17    return 0;
18}
19
20// 注意：
21// 上面的两重 for 循环位置不能交换
22// 如果交换了，那么得到的结果将会包含重复的组合（只是排列顺序不同）
23// 其含义为：在 dp[j - num[i]] 的组合末尾添加 num[i] 得到 dp[j]

  • 如何用最少的次数测出鸡蛋会在哪一层摔碎？

    https://www.zhihu.com/question/19690210

    \(\color{darkgreen}{Code}\)

     1## 作者：知乎用户
 2## 链接：https://www.zhihu.com/question/19690210/answer/18079633
 3## f(n, m)：n 层楼，m 个鸡蛋所需最少次数
 4## f(0, m) = 0
 5## f(n, 1) = n
 6## f(n, m) = min{max{f(k-1, m-1), f(n-k, m)}} + 1, 1 <= k <= n。 k 表示尝试在第 k 层扔下鸡蛋。
 7
 8import functools
 9@functools.lru_cache(maxsize=None)
10def f(n, m):
11    if n == 0:
12        return 0
13    if m == 1:
14        return n
15
16    ans = min([max([f(i - 1, m - 1), f(n - i, m)]) for i in range(1, n + 1)]) + 1
17    return ans
18
19print(f(100, 2))  # 14
20print(f(200, 2))  # 20

     1def solve(N, M):
 2    if N < 1 or M < 1:
 3        return 0
 4
 5    inf = float('inf')
 6    f = [[inf for _m in range(M+1)] for _n in range(N+1)]
 7    for m in range(M+1):
 8        f[0][m] = 0
 9        f[1][m] = 1
10    for n in range(2, N+1):
11        f[n][1] = n
12
13    for n in range(2, N+1):
14        for m in range(2, M+1):
15            for k in range(1, n+1):
16                f[n][m] = min(f[n][m], max(f[k-1][m-1], f[n-k][m]) + 1)
17
18    return f[N][M]

  • 机器人走方格。从 \((0,0)\) 走到 \((x-1,y-1)\) ，每一步只能往右或往下走。网格图 \(map\) 定义了一些障碍点（ \(map[i][j] \ne 1\) )，不能从障碍点通过。有多少种走法？ 延伸：如果没有障碍点，一共有 \(C_{(x-1)+(y-1)}^{(x-1)}\) 种走法。

    https://www.nowcoder.com/practice/b3ae8b9782af4cf29253afb2f6d6907d?tpId=8&tqId=11034&rp=1&ru=%2Fta%2Fcracking-the-coding-interview&qru=%2Fta%2Fcracking-the-coding-interview%2Fquestion-ranking

    \(\color{darkgreen}{Code}\)

     1// dp(i, j) = dp(i-1, j) + dp(i, j-1)
 2// 注意边界
 3
 4int countWays(vector<vector<int> > map, int x, int y)
 5{
 6    vector<int> dp(y, 0);
 7    if(map[0][0] != 1) dp[0] = 0; // 起点初始化
 8    else dp[0] = 1;
 9
10    for(int row = 0; row < x; ++row)
11    {
12        for(int col = 0; col < y; ++col)
13        {
14            if(row || col) // 忽略起点处
15            {
16                if(map[row][col] != 1) dp[col] = 0;
17                else
18                {
19                    long long fromUp = 0; // long long 防止溢出
20                    if(row > 0) fromUp = dp[col];
21                    long long fromLeft = 0;
22                    if(col > 0) fromLeft = dp[col-1];
23                    dp[col] = (int)((fromUp + fromLeft)%1000000007);
24                }
25            }
26        }
27    }
28    return dp[y-1];
29}

  • [LeetCode] Knight Dialer 马踏数字键盘。Hint：回溯算法超时，用动态规划，考虑空间复用。

    https://leetcode.com/problems/knight-dialer/

    \(\color{darkgreen}{Code}\)

     1class Solution
 2{
 3public:
 4    int knightDialer(int n)
 5    {
 6        if(n < 1) return 0;
 7        if(n == 1) return 10;
 8        int mod = 1000000007;
 9        const int row = 4;
10        const int col = 3;
11        vector<vector<int>> dp(2, vector<int>(row*col, 0));
12        for(int i = 0; i < row*col; ++i)
13        {
14            if(i != 9 && i != 11) dp[0][i] = 1;
15        }
16        int res = 0;
17        for(int t = 1; t < n; ++t)
18        {
19            fill(dp[t&1].begin(), dp[t&1].end(), 0); // 空间复用，需要预先清零
20            for(int i = 0; i < row*col; ++i)
21            {
22                if(i != 9 && i != 11) // 略过非数字键
23                {
24                    for(int k = 0; k < 8; ++k)
25                    {
26                        int x = i / col + mv[k][0]; // 获取行列号
27                        int y = i % col + mv[k][1];
28                        if(x < 0 || x >= row || y < 0 || y >= col) continue;
29                        dp[t&1][i] += dp[(t-1)&1][x*col+y];
30                        dp[t&1][i] %= mod;
31                    }
32                }
33                if(t == n-1) res = (res + dp[t&1][i]) % mod;
34            }
35        }
36        return res;
37    }
38private:
39    const static int mv[8][2];
40};
41const int Solution::mv[8][2] = {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};

  • \(n\) 个骰子点数之和及其频数。

    \(\color{darkgreen}{Code}\)

     1// 方法一：动态规划
 2// dp[k, n] 表示 k 个骰子，点数和为 n 的频数
 3// dp[k, n] = dp[k-1, n-1] + dp[k-1, n-2] + dp[k-1, n-3] + dp[k-1, n-4] + dp[k-1, n-5] + dp[k-1, n-6]
 4
 5vector<int> diceSum(int n)
 6{
 7  assert(n > 0);
 8  vector<vector<int>> dp(2, vector<int>(n*6+1, 0)); // n 个骰子，最大和为 6n
 9  fill(dp[1].begin()+1, dp[1].begin()+7, 1); // 1 个骰子，初始化
10
11  for (int k = 2; k <= n; ++k)
12  {
13    fill(dp[k & 1].begin(), dp[k & 1].end(), 0); // k 个骰子，最小和为 k，最大和为 6k
14    for (int s = k; s <= k * 6; ++s)
15    {
16      for (int i = 1; i <= 6 && s - i >= k-1; ++i) // k-1 个骰子，最小和为 k-1
17      {
18        dp[k & 1][s] += dp[(k - 1) & 1][s - i];
19      }
20    }
21  }
22  return dp[n & 1];
23}

    1## 方法二：多项式系数
2## 多项式 (x + x^2 + x^3 + x^4 + x^5 + x^6) ^ n 的系数就是点数和的频数，阶次对应点数和
3
4from numpy.polynomial.polynomial import Polynomial
5
6def diceSum(n):
7    ## (0 + x + x^2 + x^3 + x^4 + x^5 + x^6) ^ n
8    p = Polynomial((0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0)) ** n
9    return p.coef

  • 正则表达式匹配。pattern 中 ‘.’ 可以表示任意一个字符，’*’ 表示它前面的字符可以出现任意次（包括 0 次）。

    https://leetcode.com/problems/regular-expression-matching/

    \(\color{darkgreen}{Code}\)

     1## 动态规划，top-down
 2## dp[i][j] 表示 string：[i, len(string)) 与 pattern：[j, len(pattern)) 的匹配结果
 3## 空间复杂度：O(len(string) * len(pattern))
 4
 5class Solution(object):
 6    def isMatch(self, string, pattern):
 7        """
 8        :type s: str
 9        :type p: str
10        :rtype: bool
11        """
12        dp = [[False] * (len(pattern) + 1) for _ in range(len(string) + 1)]
13        dp[-1][-1] = True ## 初始化
14
15        for s in range(len(string), -1, -1):
16            for p in range(len(pattern)-1, -1, -1):
17                flag = s < len(string) and pattern[p] in {string[s], '.'}
18                if p+1 < len(pattern) and pattern[p+1] == '*':
19                    dp[s][p] = dp[s][p+2] or (flag and dp[s+1][p]) ## 匹配 0 次 or 多次
20                else:
21                    dp[s][p] = flag and dp[s+1][p+1]
22        return dp[0][0]

     1## 存储复用，空间复杂度：O(2 * len(pattern))
 2## 注意：有些值需要更新，不能复用错误的值
 3
 4class Solution(object):
 5    def isMatch(self, string, pattern):
 6        dp = [[False] * (len(pattern) + 1) for _ in range(2)]
 7
 8        for s in range(len(string), -1, -1):
 9            if s == len(string):
10                dp[s&1][-1] = True ## 初始化
11            else:
12                dp[s&1][-1] = False ## 由于后面的循环不会更新 dp[s&1][-1]，如果直接复用之前的值，那么一直是 True，将导致错误
13            for p in range(len(pattern)-1, -1, -1):
14                flag = s < len(string) and pattern[p] in {string[s], '.'}
15                if p+1 < len(pattern) and pattern[p+1] == '*':
16                    dp[s&1][p] = dp[s&1][p+2] or (flag and dp[(s+1)&1][p])
17                else:
18                    dp[s&1][p] = flag and dp[(s+1)&1][p+1]
19        return dp[0][0]

  • 最大子矩阵的和。Hint：行区间遍历，列区间采用动态规划，时间复杂度 \(\mathcal{O}(n^3)\) 。

    \(\color{darkgreen}{Code}\)

     1class SubMatrix
 2{
 3public:
 4    int sumOfSubMatrix(vector<vector<int> > mat, int n)
 5    {
 6        if(n <= 0) return 0;
 7        for(int r = 1; r < n; ++r)
 8        {
 9            for(int c = 0; c < n; ++c)
10            {
11                mat[r][c] += mat[r-1][c]; // 计算前 r 行和，避免后面重复计算
12            }
13        }
14        int res = INT_MIN;
15        for(int r1 = 0; r1 < n; ++r1)
16        {
17            for(int r2 = r1; r2 < n; ++r2)
18            {
19                vector<int> subMat(mat[r2].begin(), mat[r2].end());
20                if(r1 > 0)
21                {
22                    for(int c = 0; c < n; ++c) subMat[c] -= mat[r1-1][c]; // subMat 是行区间 [r1, r2] 的和
23                }
24                int dp = 0;
25                for(int c = 0; c < n; ++c)
26                {
27                    dp = max(dp + subMat[c], subMat[c]);
28                    res = max(res, dp);
29                }
30            }
31        }
32        return res;
33    }
34};

8.8. 参考资料

  1. 状态压缩DP入门