Skip to main content

第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];
}

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

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;
}