【动态规划】常见基础DP优化技巧

· · 算法·理论

前言

这是我的第一篇文章，有建议的可以私信我或评论 QwQ。
update：2026.1.31 感谢 @Jacken 指出错误。

正文

废话不多说直接开讲

1. 前缀和优化

前缀和优化 DP 常出现在计数 DP 中，此时的状态通过一段区间和来转移。

例题：AtCoder-dp_m Candies

这个题真的是典中典了。
设状态 dp_{i,j} 表示前 i 个小朋友分到 j 颗糖果，明显的，有转移：

dp_{i,j}=\sum_{k=\max(0,j-a_i)}^jdp_{i-1,k}

时间复杂度是 O(n\times k^2)，需要优化。

不难发现状态转移是个区间和，所以设 s_{i,j}=\sum_{k=0}^jdp_{i,k}，则转移就变成了 O(1) 的：

dp_{i,j}=s_{i-1,j}-s_{i-1,j-a_i-1}

时间复杂度为 O(n\times k)，可以通过本题。

代码
int main()
{
    n=read(),m=read();
    for(int i=0;i<=m;i++) s[i]=1; //滚掉一维
    for(int i=1;i<=n;i++)
    {
        int a;a=read();
        for(int j=0;j<=m;j++)
        {
            if(j<=a) dp[i][j]=(dp[i][j]+s[j])%mod;
            else dp[i][j]=(dp[i][j]+s[j]-s[j-a-1])%mod; 
        }
        s[0]=dp[i][0];
        for(int j=1;j<=m;j++) s[j]=s[j-1]+dp[i][j];
    }
    cout<<dp[n][m];
    return 0;
}

2. mx/mn 数组优化

这种优化方法一般出现在求最优解 DP 中。

例题：P1107 雷涛的小猫

也是一个经典题目了。
设状态 dp_{i,j} 表示小猫在第 j 颗柿子树的高度 i 能吃到的最大柿子数，a_{i,j} 表示这个位置有没有柿子。
在位置 (i,j) 时，小猫既可以从上面一层过来，也可以从其他树跳过来，所以有转移：

dp_{i,j}=\max_{k=1}^n\max(dp_{i+1,j},dp_{i+d,k})+a_{i,j}

时间复杂度 O(n^2\times h)，考虑优化。

不难发现柿子式子等价于：

dp_{i,j}=\max(dp_{i+1,j},\max_{k=1}^ndp_{i+d,k})+a_{i,j}

其中的 \max_{k=1}^ndp_{i+d,k} 会被反复利用，所以设 mx_i=\max_{k=1}^ndp_{i,k}，式子变为：

dp_{i,j}=\max(dp_{i+1,j},mx_{i+d})+a_{i,j}

时间复杂度 O(n\times h)，可以通过本题。

代码
int main(){
    n=read(),h=read(),d=read();
    for(int i=1;i<=n;i++)
    {
        int t,x;t=read();
        while(t--) x=read(),a[x][i]++;
    }
    for(int i=h;i>=0;i--)
    {
        for(int j=1;j<=n;j++)
        {
            dp[i][j]=max(dp[i+1][j],mx[i+t])+a[i][j];
            mx[i]=max(mx[i],dp[i][j]);
            ans=max(ans,dp[i][j]);
        }
    }
    cout<<ans;
    return 0;
}

3. 单调队列（单调栈）优化

重头戏来了！
不会模板的可以去 P1886【模板】单调队列 / 滑动窗口 和 P5788 【模板】单调栈 学习。
这种一般出现在通过区间最大值转移的 DP 优化中。

例题：P1725 琪露诺

设 dp_i 为到达位置 i 的最大值，明显地有转移：

dp_i=\max_{j=\max(0,i-r)}^{i-l}dp_j+a_i

时间复杂度 O(n^2)，需要优化。

不难发现 \max_{j=\max(0,i-r)}^{i-l}dp_j 相当于滑动窗口，所以可以拿单调队列来优化，时间复杂度 O(n)，可以通过此题。

代码
int main()
{
    n=read(),l=read(),r=read();
    for(int i=0;i<=n;i++) a[i]=read(),dp[i]=-INF;
    dp[0]=0;
    for(int i=l;i<=n;i++)
    {
        while(!q.empty()&&dp[q.back()]<dp[i-l]) q.pop_back();
        q.push_back(i-l);
        while(!q.empty()&&q.front()<i-r) q.pop_front();
        dp[i]=dp[q.front()]+a[i];
    }
    int ans=-INF;
    for(int i=n-r+1;i<=n;i++) ans=max(ans,dp[i]);//注意答案
    cout<<ans;
    return 0;
}

4. 贪心（数学）优化

这类优化一般在求最优解 DP 中出现，我感觉这类优化挺神奇的。

例题：P13957 [ICPC 2023 Nanjing R] 背包

设 dp_{i,j,l} 表示买到第 i 颗宝石，获得了 l 颗免费的宝石，花了 j 的钱的最大美丽度。要么免费拿，要么买，要么不买，所以有转移：

dp_{i,j,l}=\max(dp_{i-1,j,l},dp_{i-1,j-w_i,l}+v_i,dp_{i-1,j,l-1}+v_i)

时间复杂度 O(n\times W\times k)，需要优化。

通过贪心，不难（其实很难）发现选取 k 个价格最大的宝石是最优的，所以说我们只需要按 w_i 升序排序，设 dp_{i,j} 表示前 i 个宝石花 j 的钱的最大美丽度，然后免费的就选后 n-i 个中美丽度最大的就好了。
时间复杂度 O(n\times W+n^2\times \log n)，可以通过本题。

代码
int main()
{
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;i++) a[i].w=read(),a[i].v=read;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++) 
    {
        for(int j=m;j>=a[i].v;j--) 
            dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);
        priority_queue<int> q;
        for(int j=i+1;j<=n;j++) q.push(a[j].v);
        int qwq=dp[m];
        for(int j=1;j<=k;j++)   
            if(!q.empty()) qwq+=q.top(),q.pop();
        ans=max(ans,qwq);
    }
    cout<<ans; 
    return 0;
}

最后

你可以拿一些题练手咯：