第58章 复杂动态规划
搜索知识点 /

第58章 复杂动态规划

复杂动态规划是在基础一维动态规划之上的扩展，主要包括二维动态规划及动态规划最值优化策略。二维动态规划通过二维状态数组描述问题，适用于处理具有两个维度约束的场景（如矩阵路径、区间问题等）；最值优化则通过对状态转移方程的分析，减少冗余计算，提升算法效率。

58.1 二维动态规划

二维动态规划的状态通过两个下标定义dp[i][j]，通常用于描述与两个变量相关的子问题（如前i个元素和前j个元素的关系、矩阵中位置i,j的最优解等）。其核心是建立二维状态之间的转移关系，通过填充二维数组求解原问题。

58.1.1 矩阵最小路径和

问题定义：给定一个包含非负整数的m×n矩阵，从左上角出发，每次只能向右或向下移动，到达右下角的最小路径和。 解题思路

  • 状态定义：dp[i][j]表示从左上角(0,0)到单元格(i,j)的最小路径和。
  • 边界条件： 第一行i=0,j>0：只能从左侧移动到达，dp[0][j] = dp[0][j-1] + grid[0][j] 第一列j=0,i>0：只能从上方移动到达，dp[i][0] = dp[i-1][0] + grid[i][0]
  • 普通情况i>0,j>0：可从上方或左侧到达，取两者最小值
dp[i][j]=min⁡(dp[i−1][j],dp[i][j−1])+grid[i][j]dp[i][j] = \min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
  • 结果提取：dp[m-1][n-1]

完整代码

#include <vector>
#include <algorithm>
using namespace std;
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 j = 1; j < n; j++){
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    // 填充第一列
    for (int i = 1; i < m; i++){
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    // 填充其余单元格
    for (int i = 1; i < m; i++){
        for (int j = 1; j < n; j++){
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    return dp[m - 1][n - 1];
}

空间优化：仅保留一维数组，空间复杂度从O(mn)O(mn)降至O(n)O(n)

int minPathSumOptimized(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector<int> dp(n);
    dp[0] = grid[0][0];
    // 初始化第一行
    for (int j = 1; j < n; j++){
        dp[j] = dp[j - 1] + grid[0][j];
    }
    // 逐行计算
    for (int i = 1; i < m; i++) {
        dp[0] += grid[i][0];
        for (int j = 1; j < n; j++){
            dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];
        }
    }
    return dp[n - 1];
}

58.1.2 最长公共子序列(LCS)

问题定义：给定两个字符串s1和s2，求最长公共子序列长度（子序列不要求连续，仅保持字符顺序）。 解题思路

  • 状态定义：dp[i][j]表示s1前i个字符、s2前j个字符的最长公共子序列长度。
  • 边界条件：dp[0][j]=0、dp[i][0]=0，空串无公共字符。
  • 状态转移： 若s1[i-1] == s2[j-1]： dp[i][j]=dp[i−1][j−1]+1dp[i][j] = dp[i-1][j-1] + 1 若字符不相等： dp[i][j]=max⁡(dp[i−1][j],dp[i][j−1])dp[i][j] = \max(dp[i-1][j], dp[i][j-1])

完整二维代码

#include <vector>
#include <string>
using namespace std;
int longestCommonSubsequence(string s1, string s2) {
    int m = s1.size();
    int n = s2.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 (s1[i-1] == s2[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];
}

滚动数组空间优化

int longestCommonSubsequenceOptimized(string s1, string s2){
    int m = s1.size();
    int n = s2.size();
    vector<int> dp(n + 1, 0);
    for (int i = 1; i <= m; i++){
        int prev = 0;
        for (int j = 1; j <= n; j++){
            int temp = dp[j];
            if (s1[i-1] == s2[j-1]){
                dp[j] = prev + 1;
            }else{
                dp[j] = max(dp[j], dp[j-1]);
            }
            prev = temp;
        }
    }
    return dp[n];
}

58.1.3 最长上升子序列(LIS)

问题定义：无序整数数组，求最长严格上升子序列长度。 DP朴素解法，时间O(n2)O(n^2)

#include <vector>
#include <algorithm>
using namespace std;
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if(n == 0) return 0;
    vector<int> dp(n, 1);
    for (int i = 1; i < n; i++){
        for (int j = 0; j < i; j++){
            if (nums[i] > nums[j]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}

贪心+二分优化，时间O(nlog⁡n)O(n \log n)

int lengthOfLISOptimized(vector<int>& nums){
    vector<int> tails;
    for (int num : nums){
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()){
            tails.push_back(num);
        }else{
            *it = num;
        }
    }
    return tails.size();
}

58.1.4 区间动态规划（最长回文子序列）

问题定义：给定字符串，求最长回文子序列长度。

  • 状态定义：dp[i][j]代表字符串区间[i,j]的最长回文长度
  • 转移： {s[i]=s[j]dp[i][j]=dp[i+1][j−1]+2s[i]≠s[j]dp[i][j]=max⁡(dp[i+1][j],dp[i][j−1])\begin{cases} s[i] = s[j] & dp[i][j] = dp[i+1][j-1] + 2 \\ s[i] \neq s[j] & dp[i][j] = \max(dp[i+1][j], dp[i][j-1]) \end{cases}
  • 边界：i==j时dp[i][j]=1；i>j为0 完整二维代码
#include <vector>
#include <string>
using namespace std;
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;
    }
    // 按区间长度从小到大遍历
    for (int l = 2; l <= n; l++){
        for (int i = 0; i <= n - l; i++){
            int j = i + l - 1;
            if(s[i] == s[j]){
                if(l == 2){
                    dp[i][j] = 2;
                }else{
                    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];
}

58.2 动态规划最值优化

动态规划最值优化，针对转移方程中重复max/min枚举大量前驱的场景，通过单调队列、单调栈降低时间复杂度。

58.2.1 适用特征

状态转移需要遍历多个前置状态取最值，暴力枚举会带来O(n2)O(n^2)高复杂度。

58.2.2 单调性优化（单调队列）

以滑动窗口最大值为基础示例（优化思想通用）

#include <vector>
#include <deque>
using namespace std;
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> res;
    deque<int> q;
    for(int i = 0; i < nums.size(); i++){
        // 移除窗口外下标
        while(!q.empty() && q.front() <= i - k){
            q.pop_front();
        }
        // 队尾小于当前值全部弹出，保持递减队列
        while(!q.empty() && nums[q.back()] <= nums[i]){
            q.pop_back();
        }
        q.push_back(i);
        // 窗口形成后记录答案
        if(i >= k - 1){
            res.push_back(nums[q.front()]);
        }
    }
    return res;
}

## 58.3 选择题练习（含参考答案）

<details>
<summary>参考答案与解析（点击展开）</summary>

1. **A** —— `dp[i][j]` 表示 s1 的前 $i$ 个字符与 s2 的前 $j$ 个字符的 LCS 长度（常用"前 i 个"的 1-based 定义）。
2. **B** —— LIS 贪心+二分将时间从 $O(n^2)$ 降到 $O(n\log n)$。
3. **B** —— 滚动数组用一维数组代替二维数组，主要把空间复杂度从 $O(mn)$ 降到 $O(\min(m,n))$，优化的是**空间**。
4. **B** —— 区间 DP 先算短区间、再算长区间，通常按"区间长度从小到大"枚举。
5. **B** —— 当 $s[i]=s[j]$ 且区间长度 $>2$ 时，两端字符都可纳入，转移为 $dp[i+1][j-1]+2$。

</details>

1. 在最长公共子序列（LCS）中，`dp[i][j]` 通常表示？（　　）
   - A. s1 前 $i$ 个字符与 s2 前 $j$ 个字符的最长公共子序列长度
   - B. s1 前 $i$ 个字符与 s2 前 $j$ 个字符的最长公共子串长度
   - C. s1 第 $i$ 个字符的值
   - D. 两字符串的总长度

2. 最长上升子序列（LIS）的"贪心 + 二分"优化，时间复杂度为？（　　）
   - A. $O(n^2)$
   - B. $O(n\log n)$
   - C. $O(n)$
   - D. $O(2^n)$

3. 使用"滚动数组"优化动态规划，主要优化的是？（　　）
   - A. 时间复杂度
   - B. 空间复杂度
   - C. 代码可读性
   - D. 数值精度

4. 区间动态规划（如最长回文子序列）通常按什么顺序枚举区间？（　　）
   - A. 按起点 $i$ 从小到大即可
   - B. 按区间长度从小到大
   - C. 随机枚举
   - D. 按终点 $j$ 从大到小

5. 最长回文子序列中，当 $s[i]=s[j]$ 且区间长度大于 2 时，状态转移应为？（　　）
   - A. $dp[i][j]=dp[i+1][j-1]+1$
   - B. $dp[i][j]=dp[i+1][j-1]+2$
   - C. $dp[i][j]=\max(dp[i+1][j],dp[i][j-1])$
   - D. $dp[i][j]=dp[i][j-1]$
SShowball OI知识手册