返回首页 C++ 模板

进阶动态规划

二维DP、区间DP、LIS/LCS、滚动数组优化——DP 从入门到进阶

二维DP 区间DP LIS LCS 滚动数组 GESP7 
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
const int INF = 0x3f3f3f3f;

// ========== 1. 二维DP：矩阵路径 ==========
// 从左上角到右下角，只能向右或向下，求路径最大和
void matrix_path() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];

    vector<vector<int>> dp(n, vector<int>(m, 0));
    dp[0][0] = a[0][0];
    for (int i = 1; i < n; i++) dp[i][0] = dp[i-1][0] + a[i][0];
    for (int j = 1; j < m; j++) dp[0][j] = dp[0][j-1] + a[0][j];
    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++)
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j];

    cout << dp[n-1][m-1] << endl;
}

// ========== 2. 区间DP：石子合并 ==========
// 相邻两堆石子合并，代价为两堆之和，求最小总代价
void stone_merge() {
    int n;
    cin >> n;
    vector<int> a(n + 1), sum(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }

    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

    // 枚举区间长度
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = INF;
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j],
                    dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]);
            }
        }
    }

    cout << dp[1][n] << endl;
}

// ========== 3. LIS 最长上升子序列 ==========
// O(n²) 版本
int lis_n2(vector<int> &a) {
    int n = a.size();
    vector<int> dp(n, 1);
    int ans = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}

// O(n log n) 版本：贪心+二分
int lis_nlogn(vector<int> &a) {
    vector<int> tails;  // tails[i]: 长度为 i+1 的上升子序列末尾最小值
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}

// ========== 4. LCS 最长公共子序列 ==========
int lcs(string &a, string &b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i-1] == b[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[n][m];
}

// ========== 5. 滚动数组优化 ==========
// 以 LCS 为例，空间从 O(nm) 降到 O(m)
int lcs_optimized(string &a, string &b) {
    int n = a.size(), m = b.size();
    vector<int> prev(m + 1, 0), curr(m + 1, 0);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i-1] == b[j-1])
                curr[j] = prev[j-1] + 1;
            else
                curr[j] = max(prev[j], curr[j-1]);
        }
        swap(prev, curr);
        fill(curr.begin(), curr.end(), 0);
    }
    return prev[m];
}

// ========== 6. 完全背包 ==========
// 每种物品可以使用无限次
void complete_knapsack() {
    int n, W;
    cin >> n >> W;
    vector<int> dp(W + 1, 0);

    for (int i = 0; i < n; i++) {
        int w, v;
        cin >> w >> v;
        for (int j = w; j <= W; j++) {   // 正序！与01背包相反
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
    cout << dp[W] << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string a = "ABCBDAB", b = "BDCAB";
    cout << "LCS: " << lcs(a, b) << endl;  // 4 (BCAB)

    return 0;
}

📖 要点说明

DP 进阶路线

一维DP → 二维DP → 区间DP → 状压DP / 树形DP

区间 DP 模板

for (len = 2; len <= n; len++)       // 枚举区间长度
    for (i = 1; i + len - 1 <= n; i++)  // 枚举左端点
        j = i + len - 1;               // 右端点
        for (k = i; k < j; k++)       // 枚举分割点
            dp[i][j] = min/max(dp[i][j], dp[i][k] + dp[k+1][j] + cost);

滚动数组

LIS 两种复杂度

版本 时间 适用
O(n²) 慢 n ≤ 10³
O(n log n) 快 n ≤ 10⁵

⚠️ 常见错误