DP 优化

概念讲解

什么是 DP 优化？

DP 优化是降低动态规划时间复杂度的技巧。

单调队列优化

适用场景

状态转移方程形如：dp[i] = min/max(dp[j] + f(i, j))，其中 j 在一个滑动窗口内。

实现

1234567891011121314151617181920const int N = 100005;
int dp[N];
deque<int> dq;

void push(int i) {
    while (!dq.empty() && dp[dq.back()] >= dp[i]) {
        dq.pop_back();
    }
    dq.push_back(i);
}

void pop(int i, int k) {
    while (!dq.empty() && dq.front() < i - k) {
        dq.pop_front();
    }
}

int query() {
    return dp[dq.front()];
}

斜率优化

适用场景

状态转移方程形如：dp[i] = min(dp[j] + f(i, j))，可以转化为斜率形式。

实现

1234// dp[i] = min(dp[j] + (x[i] - x[j])^2)
// 转化为：dp[j] + x[j]^2 = 2 * x[i] * x[j] + dp[i] - x[i]^2
// 斜率：2 * x[i]
// 截距：dp[i] - x[i]^2

矩阵快速幂优化

适用场景

线性递推关系。

实现

1// 参考矩阵快速幂知识点

考点分析

初赛考查方式

  1. 选择题： DP 优化的概念
  2. 程序阅读： 理解 DP 优化
  3. 编程题： DP 优化应用

常见题型

  • 单调队列优化
  • 斜率优化
  • 矩阵快速幂优化

例题精讲

例题 1：单调队列优化

题目： 滑动窗口最小值。

解答：

12345678910111213141516171819202122232425262728293031323334#include <iostream>
#include <deque>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    deque<int> dq;
    
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }
        
        while (!dq.empty() && a[dq.back()] >= a[i]) {
            dq.pop_back();
        }
        
        dq.push_back(i);
        
        if (i >= k - 1) {
            cout << a[dq.front()] << " ";
        }
    }
    cout << endl;
    
    return 0;
}

练习题

  1. 洛谷 P1886 滑动窗口
查看答案

思路：单调队列维护窗口内的最小值和最大值。

123456789101112131415161718192021222324252627282930313233#include <iostream>
#include <deque>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    
    // 最小值
    deque<int> dq;
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && dq.front() < i - k + 1) dq.pop_front();
        while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) cout << a[dq.front()] << " ";
    }
    cout << endl;
    
    // 最大值
    dq.clear();
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && dq.front() < i - k + 1) dq.pop_front();
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) cout << a[dq.front()] << " ";
    }
    cout << endl;
    
    return 0;
}
  1. 洛谷 P2627 Mowing the Lawn G
查看答案

思路：单调队列优化 DP。

123456789101112131415161718192021222324252627282930313233#include <iostream>
#include <deque>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    
    long long e[n + 1], prefix[n + 1];
    prefix[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> e[i];
        prefix[i] = prefix[i - 1] + e[i];
    }
    
    long long dp[n + 1];
    dp[0] = 0;
    deque<int> dq;
    dq.push_back(0);
    
    for (int i = 1; i <= n; i++) {
        while (!dq.empty() && dq.front() < i - k - 1) dq.pop_front();
        dp[i] = dp[dq.front()] + prefix[i] - prefix[dq.front() + 1];
        
        while (!dq.empty() && dp[dq.back()] - prefix[dq.back() + 1] >= dp[i] - prefix[i + 1]) {
            dq.pop_back();
        }
        dq.push_back(i);
    }
    
    cout << dp[n] << endl;
    return 0;
}
  1. 洛谷 P3628 [APIO2010] 特别行动队
查看答案

思路：斜率优化 DP。

1234567891011121314151617181920212223242526272829303132333435363738394041424344#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    long long a, b, c;
    cin >> a >> b >> c;
    
    long long x[n + 1], prefix[n + 1];
    prefix[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
        prefix[i] = prefix[i - 1] + x[i];
    }
    
    long long dp[n + 1];
    dp[0] = 0;
    int q[n + 1], head = 0, tail = 0;
    q[0] = 0;
    
    for (int i = 1; i <= n; i++) {
        while (head < tail && 
               (dp[q[head + 1]] - dp[q[head]]) > 
               2 * a * prefix[i] * (prefix[q[head + 1]] - prefix[q[head]])) {
            head++;
        }
        
        int j = q[head];
        dp[i] = dp[j] + a * (prefix[i] - prefix[j]) * (prefix[i] - prefix[j]) 
                + b * (prefix[i] - prefix[j]) + c;
        
        while (head < tail && 
               (dp[q[tail]] - dp[q[tail - 1]]) * (prefix[i] - prefix[q[tail]]) < 
               (dp[i] - dp[q[tail]]) * (prefix[q[tail]] - prefix[q[tail - 1]])) {
            tail--;
        }
        q[++tail] = i;
    }
    
    cout << dp[n] << endl;
    return 0;
}

易错点

⚠️ 注意：

  1. DP 优化要找到合适的优化方式
  2. 单调队列要注意维护单调性
  3. 斜率优化要注意凸包的维护
  4. DP 优化是动态规划的高级内容