DP...

Lywh_ddAC · 2025-09-26 19:38:57 · 算法·理论

不是？信息学这么久了，才想起来好好理解一下动态规划？
讲了那么久dp优化半句不懂，才想起来要补一下dp？

首先先记住，dp题的解题思路通常为：
读懂题意，设计状态，确定目标态和初始态，思考转移方程，思考优化。

OI Wiki

初学dp题单，中型dp题单

一个一个来吧

线性dp

一维dp，多做两道题就能get到。

B3636 文字工作，B3635 硬币问题 ，P2842 纸币问题 1

好吧有人说这也算线性dp：
SP15637 GNYR04H - Mr Youngs Picture Permutations

背包

01背包

就是先枚举物品，再枚举时间，按照常用的一维写法，要注意时间要倒着枚举，不然有可能会错用本次修改的值。
至于为什么先枚举物品，再枚举时间，就能保证一个物体只选一次呢，会发现针对每一个dp[j]，v[i]始终只会加一次。

例题：P1926 小书童——刷题大军

    for(int i=1;i<=m;i++){//针对前i个作业 
        for(int j=r;j>=1;j--){//花j的时间 
            if(j>=w[i]) 
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }

当然，不要压缩的话就要继承：

    for(int i=1;i<=m;i++){//针对前i个作业 
        for(int j=1;j<=r;j++){//花j的时间 
            if(j>=w[i]) 
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//继承上边
                //可以保证dp[i-1][l~r]是一定没有加过v[i]的
        }
    }

注意，压缩是常用的手段，用来减少空间负担，如果不的话，有几个限制条件就需要定义几维。

完全背包

不同理，先枚举时间，再枚举物品，为的就是能在相同时间下重复计算。

例题：P1616 疯狂的采药

    for(int i=1;i<=t;i++){//先枚举时间
        for(int j=1;j<=m;j++){//再枚举物品
            if(i-a[j]>=0)
                dp[i]=max(dp[i],dp[i-a[j]]+b[j]);
        }
    }

同样的，转移方程也能压缩，但这时时间就要正着枚举了，因为就是要重复计算。

数位dp

都说数位dp简单，没想到现在为止，才做了两道真正意义上的数位dp的题？

例题：P4124 [CQOI2016] 手机号码
很清新的题解，感觉应该看看就能明白：题解

数位dp较其他dp不同的一点在于，它一般是由记忆化搜索实现的，确实没有什么思维上需要跨越的东西，一般就是实现起来考码力，有的大佬写的就很简洁，有的就很冗长（不是我）。

唯一有一点初学可能会顿的地方就是，一般都会有一个判断是否严格小于或者是否顶格的东西，其实也不难理解。
比如从前往后对于每一个数位填数时，为了不超出限定范围，如果此位以前有高位（至少一位）是小于同位的上线的，那么这一位填啥都可以（不会超范围），但如果以前的所有位数都是顶着上限开的，那么此位就一定不能超过当前位的上限。

状压dp

例题：P3052 [USACO12MAR] Cows in a Skyscraper G

还能理解的一篇题解，题解 P3052

像这种普通dp写不出来的，数据范围又不是太大的，可以想到状压dp。