多维动态规划：在更高维度思考

当一个维度不够用时,就多加一个维度!

什么是多维动态规划

多维动态规划是动态规划的扩展,使用多个维度的状态来描述问题。如果说一维DP是一条线,那么二维DP就是一个平面,三维DP则是一个立体空间。

核心思想:当问题需要多个参数才能描述清楚状态时,就需要使用多维DP

形象理解

想象你在玩一个游戏:

1
2
3
一维DP: 在一条路上前进,只需要记录"到达第i个位置"
二维DP: 在一个网格中移动,需要记录"到达坐标(i,j)"
三维DP: 在多个物品中选择,需要记录"前i个物品,容量为j,价值为k"

就像从一维数轴进化到二维平面,再到三维空间!

从一维到多维的思维跃迁

维度增加的必要性

graph TD
    A[问题复杂度] --> B{一个参数够吗?}
    B -->|够| C[一维DP]
    B -->|不够| D{两个参数够吗?}
    D -->|够| E[二维DP]
    D -->|不够| F[三维/更高维DP]
    
    style A fill:#FFE4B5
    style E fill:#90EE90
    style F fill:#87CEEB

什么时候用多维DP?

场景 维度 示例
路径问题 二维 网格中的最短路径
双序列匹配 二维 最长公共子序列
背包问题 二维/三维 01背包、多重背包
区间问题 二维 戳气球、合并石头
状态机问题 多维 买卖股票

二维DP经典问题

1. 不同路径 (LeetCode 62)

一个机器人位于一个 m×n 网格的左上角,每次只能向下或向右移动,问到达右下角有多少条不同的路径?

问题分析

1
2
3
4
5
网格: 3×7
起点: (0,0)
终点: (2,6)

每次只能: 向右 或 向下

可视化理解

1
2
3
4
5
起点→ □ □ □ □ □ □
      □ □ □ □ □ □
      □ □ □ □ □ ← 终点

到达(i,j)的方式 = 从(i-1,j)向下 + 从(i,j-1)向右

状态定义

1
dp[i][j]: 到达位置(i,j)的不同路径数

状态转移方程

1
2
3
dp[i][j] = dp[i-1][j] + dp[i][j-1]
            ↑            ↑
          从上方来    从左方来

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 方法1: 二维DP数组
int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 1));
    
    // 第一行和第一列都只有一种走法
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    
    return dp[m-1][n-1];
}

// 方法2: 空间优化 - 滚动数组
int uniquePaths(int m, int n) {
    vector<int> dp(n, 1);
    
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[j] = dp[j] + dp[j-1];
                    ↑        ↑
                  上方     左方
        }
    }
    
    return dp[n-1];
}

时间复杂度: O(m×n)
空间复杂度: O(m×n) → 优化后 O(n)

执行过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
m=3, n=7

初始状态 (第一行和第一列都是1):
1  1  1  1  1  1  1
1  ?  ?  ?  ?  ?  ?
1  ?  ?  ?  ?  ?  ?

计算过程:
1  1  1   1   1   1   1
1  2  3   4   5   6   7
1  3  6  10  15  21  28
      ↑
    dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3

答案: 28种路径

2. 最小路径和 (LeetCode 64)

给定一个包含非负整数的 m×n 网格,找到一条从左上角到右下角的路径,使得路径上的数字总和最小

问题分析

1
2
3
4
5
6
7
输入:
1  3  1
1  5  1
4  2  1

输出: 7
路径: 1→3→1→1→1 = 7

状态定义

1
dp[i][j]: 从(0,0)到(i,j)的最小路径和

状态转移方程

1
2
3
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
                          ↑             ↑
                        从上方来      从左方来

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    
    vector<vector<int>> dp(m, vector<int>(n));
    
    // 初始化起点
    dp[0][0] = grid[0][0];
    
    // 初始化第一列
    for (int i = 1; i < m; ++i) {
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }
    
    // 初始化第一行
    for (int j = 1; j < n; ++j) {
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }
    
    // 状态转移
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
        }
    }
    
    return dp[m-1][n-1];
}

时间复杂度: O(m×n)
空间复杂度: O(m×n)

执行过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
grid:
1  3  1
1  5  1
4  2  1

DP过程:
1  4  5     ← 第一行: 累加
↓
2  7  6     ← dp[1][1] = 5 + min(4,2) = 7
↓
6  8  7     ← dp[2][2] = 1 + min(6,8) = 7
       ↑
      答案

最小路径和: 7

3. 最长公共子序列 (LeetCode 1143)

给定两个字符串,求它们的最长公共子序列长度

问题分析

1
2
3
4
text1 = "abcde"
text2 = "ace"

最长公共子序列: "ace" (长度为3)

双序列DP的精髓

这是典型的双序列匹配问题,需要同时追踪两个序列的位置!

状态定义

1
dp[i][j]: text1前i个字符 与 text2前j个字符 的最长公共子序列长度

状态转移方程

1
2
3
4
5
6
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])
                    ↑            ↑
                跳过text1[i]  跳过text2[j]

可视化理解

1
2
3
4
5
6
7
    ""  a  c  e
""   0  0  0  0
a    0  1  1  1  ← text1[0]='a' == text2[0]='a', dp[1][1]=1
b    0  1  1  1
c    0  1  2  2  ← text1[2]='c' == text2[1]='c', dp[3][2]=2
d    0  1  2  2
e    0  1  2  3  ← text1[4]='e' == text2[2]='e', dp[5][3]=3

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size();
    int n = text2.size();
    
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (text1[i-1] == text2[j-1]) {
                // 字符匹配,长度+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];
}

时间复杂度: O(m×n)
空间复杂度: O(m×n)

完整执行过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
text1 = "abcde"
text2 = "ace"

DP表:
      ""  a  c  e
  ""   0  0  0  0
  a    0  1  1  1
  b    0  1  1  1
  c    0  1  2  2
  d    0  1  2  2
  e    0  1  2  3

关键步骤:
- dp[1][1]: 'a'=='a', dp[1][1]=dp[0][0]+1=1
- dp[3][2]: 'c'=='c', dp[3][2]=dp[2][1]+1=2
- dp[5][3]: 'e'=='e', dp[5][3]=dp[4][2]+1=3

答案: 3

4. 编辑距离 (LeetCode 72)

给定两个单词,计算从一个单词转换成另一个单词所需的最少操作数。允许的操作:插入、删除、替换

问题分析

1
2
3
4
5
6
7
8
9
word1 = "horse"
word2 = "ros"

操作序列:
horse → rorse (替换 h→r)
rorse → rose  (删除 r)
rose  → ros   (删除 e)

共3步

状态定义

1
dp[i][j]: word1前i个字符 转换为 word2前j个字符 的最少操作数

状态转移方程

1
2
3
4
5
6
7
8
if (word1[i-1] == word2[j-1]):
    dp[i][j] = dp[i-1][j-1]  // 字符相同,不需要操作
else:
    dp[i][j] = 1 + min({
        dp[i-1][j],    // 删除word1[i]
        dp[i][j-1],    // 插入word2[j]
        dp[i-1][j-1]   // 替换word1[i]为word2[j]
    })

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int minDistance(string word1, string word2) {
    int m = word1.size();
    int n = word2.size();
    
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    
    // 初始化:空串转换需要的操作数
    for (int i = 0; i <= m; ++i) {
        dp[i][0] = i;  // 删除所有字符
    }
    for (int j = 0; j <= n; ++j) {
        dp[0][j] = j;  // 插入所有字符
    }
    
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (word1[i-1] == word2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = 1 + min({
                    dp[i-1][j],      // 删除
                    dp[i][j-1],      // 插入
                    dp[i-1][j-1]     // 替换
                });
            }
        }
    }
    
    return dp[m][n];
}

时间复杂度: O(m×n)
空间复杂度: O(m×n)

执行过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
word1 = "horse"
word2 = "ros"

DP表:
      ""  r  o  s
  ""   0  1  2  3
  h    1  1  2  3
  o    2  2  1  2
  r    3  2  2  2
  s    4  3  3  2
  e    5  4  4  3
              ↑
            答案

关键步骤:
- dp[2][2]: 'o'=='o', dp[2][2]=dp[1][1]=1
- dp[3][1]: 'r'=='r', dp[3][1]=dp[2][0]=2
- dp[4][3]: 's'=='s', dp[4][3]=dp[3][2]=2

答案: 3步

5. 买卖股票的最佳时机III (LeetCode 123)

给定一个数组,最多可以完成两笔交易,求最大利润

问题分析

这是一个状态机DP问题,需要追踪:

  • 当前第几天
  • 当前处于什么状态(持有/不持有股票)
  • 完成了几次交易

状态定义

1
2
3
4
buy1[i]:  第i天,第一次买入后的最大利润
sell1[i]: 第i天,第一次卖出后的最大利润
buy2[i]:  第i天,第二次买入后的最大利润
sell2[i]: 第i天,第二次卖出后的最大利润

状态转移方程

1
2
3
4
buy1[i]  = max(buy1[i-1], -prices[i])
sell1[i] = max(sell1[i-1], buy1[i-1] + prices[i])
buy2[i]  = max(buy2[i-1], sell1[i-1] - prices[i])
sell2[i] = max(sell2[i-1], buy2[i-1] + prices[i])

状态转移图

graph LR
    A[初始] -->|买入| B[持有1]
    B -->|卖出| C[完成1笔]
    C -->|买入| D[持有2]
    D -->|卖出| E[完成2笔]
    
    style A fill:#FFE4B5
    style C fill:#90EE90
    style E fill:#87CEEB

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maxProfit(vector<int>& prices) {
    int n = prices.size();
    if (n == 0) return 0;
    
    // 初始化
    int buy1 = -prices[0], sell1 = 0;
    int buy2 = -prices[0], sell2 = 0;
    
    for (int i = 1; i < n; ++i) {
        buy1 = max(buy1, -prices[i]);
        sell1 = max(sell1, buy1 + prices[i]);
        buy2 = max(buy2, sell1 - prices[i]);
        sell2 = max(sell2, buy2 + prices[i]);
    }
    
    return sell2;
}

时间复杂度: O(n)
空间复杂度: O(1)

执行过程

1
2
3
4
5
6
7
8
9
10
11
12
prices = [3,3,5,0,0,3,1,4]

Day 0: buy1=-3, sell1=0, buy2=-3, sell2=0
Day 1: buy1=-3, sell1=0, buy2=-3, sell2=0
Day 2: buy1=-3, sell1=2, buy2=-1, sell2=2
Day 3: buy1=-3, sell1=2, buy2=2, sell2=2
Day 4: buy1=-3, sell1=2, buy2=2, sell2=2
Day 5: buy1=-3, sell1=2, buy2=2, sell2=5
Day 6: buy1=-3, sell1=2, buy2=2, sell2=5
Day 7: buy1=-3, sell1=2, buy2=2, sell2=6

答案: 6 (在0买入,在3卖出,再在3买入,在4卖出)

三维DP问题

01背包问题 (经典)

有n个物品和一个容量为W的背包,每个物品有重量w[i]和价值v[i],每个物品只能选一次,求最大价值

问题分析

1
2
3
4
5
6
7
物品: [(重量,价值)]
物品1: (2, 3)
物品2: (3, 4)
物品3: (4, 5)
背包容量: 5

最优方案: 选物品1和2,价值=7

状态定义

1
dp[i][j]: 前i个物品,容量为j时的最大价值

状态转移方程

1
2
3
4
dp[i][j] = max(
    dp[i-1][j],              // 不选第i个物品
    dp[i-1][j-w[i]] + v[i]   // 选第i个物品
)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 二维DP
int knapsack(vector<int>& w, vector<int>& v, int W) {
    int n = w.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= W; ++j) {
            // 不选第i个物品
            dp[i][j] = dp[i-1][j];
            
            // 如果能选第i个物品
            if (j >= w[i-1]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]] + v[i-1]);
            }
        }
    }
    
    return dp[n][W];
}

// 空间优化:一维DP (从后向前遍历)
int knapsack(vector<int>& w, vector<int>& v, int W) {
    int n = w.size();
    vector<int> dp(W + 1, 0);
    
    for (int i = 0; i < n; ++i) {
        // 必须从后向前,否则会重复使用同一物品
        for (int j = W; j >= w[i]; --j) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    
    return dp[W];
}

时间复杂度: O(n×W)
空间复杂度: O(n×W) → 优化后 O(W)

为什么要从后向前?

1
2
3
4
5
6
7
8
从前向后:
dp[2] = dp[2-w[0]] + v[0]  // 使用了w[0]
dp[4] = dp[4-w[0]] + v[0]  // 又使用了w[0]! ❌重复使用

从后向前:
dp[4] = dp[4-w[0]] + v[0]  // 使用旧的dp[2]
dp[2] = dp[2-w[0]] + v[0]  // 使用旧的dp[0]
✓ 每个物品只用一次

最长回文子序列 (LeetCode 516)

给定一个字符串,找到其中最长的回文子序列长度

问题分析

1
2
3
输入: "bbbab"
输出: 4
解释: 最长回文子序列是 "bbbb"

区间DP思想

这是区间DP的典型问题,需要思考:

  • 子串[i,j]的答案
  • 如何从更小的区间推导

状态定义

1
dp[i][j]: 字符串[i,j]区间内的最长回文子序列长度

状态转移方程

1
2
3
4
if (s[i] == s[j]):
    dp[i][j] = dp[i+1][j-1] + 2
else:
    dp[i][j] = max(dp[i+1][j], dp[i][j-1])

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int longestPalindromeSubseq(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    // 单个字符都是回文
    for (int i = 0; i < n; ++i) {
        dp[i][i] = 1;
    }
    
    // 从长度2开始枚举
    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i + len - 1 < n; ++i) {
            int j = i + len - 1;
            
            if (s[i] == s[j]) {
                dp[i][j] = dp[i+1][j-1] + 2;
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    
    return dp[0][n-1];
}

时间复杂度: O(n²)
空间复杂度: O(n²)

执行过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
s = "bbbab"

DP表 (下三角未使用):
      0  1  2  3  4
  0   1  2  3  4  4
  1   -  1  2  3  3
  2   -  -  1  2  2
  3   -  -  -  1  1
  4   -  -  -  -  1

计算顺序 (按长度递增):
len=1: 对角线全为1
len=2: dp[0][1], dp[1][2], dp[2][3], dp[3][4]
len=3: dp[0][2], dp[1][3], dp[2][4]
len=4: dp[0][3], dp[1][4]
len=5: dp[0][4]

答案: dp[0][4] = 4 ("bbbb")

多维DP优化技巧

1. 滚动数组

当dp[i][j]只依赖dp[i-1][…]时:

1
2
3
4
5
6
7
8
9
10
11
// 原始: O(m×n)空间
vector<vector<int>> dp(m, vector<int>(n));

// 优化: O(n)空间
vector<int> prev(n), curr(n);
for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
        curr[j] = ...;  // 使用prev[j]等
    }
    swap(prev, curr);
}

2. 倒序遍历 (01背包)

1
2
3
4
5
6
7
8
9
// ❌ 正序会重复使用
for (int j = 0; j <= W; ++j) {
    dp[j] = max(dp[j], dp[j-w] + v);
}

// ✓ 倒序避免重复
for (int j = W; j >= w; --j) {
    dp[j] = max(dp[j], dp[j-w] + v);
}

3. 状态压缩

某些问题可以用位运算压缩状态:

1
2
3
// 例如:旅行商问题 (TSP)
// dp[state][i]: 访问状态为state,当前在城市i的最短距离
// state用二进制表示: 101表示访问了城市0和2

多维DP问题分类

路径问题

graph LR
    A[路径问题] --> B[不同路径]
    A --> C[最小路径和]
    A --> D[地下城游戏]
    
    style A fill:#FFE4B5
    style B fill:#90EE90

特点: 在网格中移动,dp[i][j]表示到达(i,j)的状态

双序列匹配

graph LR
    A[双序列] --> B[最长公共子序列]
    A --> C[编辑距离]
    A --> D[不同的子序列]
    
    style A fill:#87CEEB

特点: 两个字符串/数组,dp[i][j]表示处理到第i和第j个字符

区间DP

graph LR
    A[区间DP] --> B[最长回文子序列]
    A --> C[戳气球]
    A --> D[合并石头]
    
    style A fill:#DDA0DD

特点: dp[i][j]表示区间[i,j]的答案,按区间长度递增计算

背包DP

graph LR
    A[背包DP] --> B[01背包]
    A --> C[完全背包]
    A --> D[多重背包]
    
    style A fill:#F0E68C

特点: 选或不选,dp[i][j]表示前i个物品,容量为j的最优解

解题思路总结

步骤1: 确定维度

1
2
3
4
问题需要几个参数描述?
- 1个参数 → 一维DP
- 2个参数 → 二维DP
- 更多 → 三维/更高维DP

步骤2: 定义状态

1
2
3
4
5
6
dp[i][j] 代表什么含义?

常见定义:
- dp[i][j]: 到达(i,j)的...
- dp[i][j]: 前i个...前j个...的...
- dp[i][j]: 区间[i,j]的...

步骤3: 找状态转移

1
2
3
4
5
6
当前状态从哪些状态转移而来?

常见转移:
- 最优化: max/min
- 计数: 累加
- 判断: 逻辑或/与

步骤4: 初始化

1
2
3
4
确定边界条件:
- dp[0][0] = ?
- dp[i][0] = ?
- dp[0][j] = ?

步骤5: 确定计算顺序

1
2
3
4
保证计算dp[i][j]时,依赖的状态已经计算:
- 从小到大 (大多数情况)
- 按长度递增 (区间DP)
- 倒序 (01背包)

常见陷阱与技巧

陷阱1: 索引混淆

1
2
3
4
5
6
7
8
9
10
11
12
// ❌ 数组越界
dp[i][j] = dp[i-1][j-1] + 1;  // 当i=0或j=0时越界

// ✓ 正确处理
for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= n; ++j) {
        // 使用i-1, j-1访问原数组
        if (text1[i-1] == text2[j-1]) {
            dp[i][j] = dp[i-1][j-1] + 1;
        }
    }
}

陷阱2: 初始化错误

1
2
3
4
5
6
// ❌ 忘记初始化边界
vector<vector<int>> dp(m, vector<int>(n));

// ✓ 正确初始化
vector<vector<int>> dp(m, vector<int>(n, 0));
// 或者显式处理第一行第一列

陷阱3: 遍历顺序错误

1
2
3
4
5
6
7
8
9
// ❌ 01背包正序遍历
for (int j = 0; j <= W; ++j) {  // 会重复使用物品
    dp[j] = max(dp[j], dp[j-w] + v);
}

// ✓ 倒序遍历
for (int j = W; j >= w; --j) {
    dp[j] = max(dp[j], dp[j-w] + v);
}

技巧1: 画表格辅助思考

1
2
3
4
5
6
7
8
9
对于双序列问题,画出DP表格:

      ""  a  c  e
  ""   0  0  0  0
  a    0  ?  ?  ?
  b    0  ?  ?  ?
  c    0  ?  ?  ?

思考每个?如何填

技巧2: 从简单例子入手

1
2
3
4
不要一开始就想复杂情况:
1. 先考虑n=1, n=2的情况
2. 找规律,推导状态转移
3. 验证边界条件

技巧3: 记住经典模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 双序列模板
for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= n; ++j) {
        if (条件) {
            dp[i][j] = ...;
        } else {
            dp[i][j] = ...;
        }
    }
}

// 区间DP模板
for (int len = 2; len <= n; ++len) {
    for (int i = 0; i + len - 1 < n; ++i) {
        int j = i + len - 1;
        dp[i][j] = ...;
    }
}

思维导图

graph TD
    A[多维DP] --> B[问题类型]
    A --> C[核心技巧]
    A --> D[优化方法]
    
    B --> B1[路径问题]
    B --> B2[双序列匹配]
    B --> B3[区间DP]
    B --> B4[背包DP]
    
    C --> C1[确定维度]
    C --> C2[定义状态]
    C --> C3[状态转移]
    C --> C4[初始化]
    
    D --> D1[滚动数组]
    D --> D2[倒序遍历]
    D --> D3[状态压缩]
    
    style A fill:#FFE4B5
    style B fill:#90EE90
    style C fill:#87CEEB
    style D fill:#DDA0DD

总结

核心要点

  1. 多维DP = 多个参数描述状态
  2. 二维是最常见的: 路径、双序列、背包
  3. 画表格: 辅助理解状态转移
  4. 注意边界: 初始化和索引处理
  5. 空间优化: 滚动数组、倒序遍历

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// 二维DP模板 (双序列)
int solve(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    // 初始化第一行和第一列
    for (int i = 0; i <= m; ++i) dp[i][0] = ...;
    for (int j = 0; j <= n; ++j) dp[0][j] = ...;
    
    // 状态转移
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + ...;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    
    return dp[m][n];
}

// 01背包模板 (空间优化)
int knapsack(vector<int>& w, vector<int>& v, int W) {
    vector<int> dp(W + 1, 0);
    
    for (int i = 0; i < n; ++i) {
        for (int j = W; j >= w[i]; --j) {  // 倒序!
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    
    return dp[W];
}

// 区间DP模板
int solve(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    // 初始化单个元素
    for (int i = 0; i < n; ++i) {
        dp[i][i] = 1;
    }
    
    // 按长度递增
    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i + len - 1 < n; ++i) {
            int j = i + len - 1;
            
            if (s[i] == s[j]) {
                dp[i][j] = dp[i+1][j-1] + 2;
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    
    return dp[0][n-1];
}

推荐练习:

推荐阅读: