动态规划

ZHONGZIJIE0608 · 2024-07-22 20:28:21 · 个人记录

简介

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。

在 OI 中，有时也把计数和递推也不严谨地称为 DP。

使用条件

最优子结构，不然没法“大事化小小事化了”。
无后效性，不然没法往后推。
子问题重叠，不然你重复求解不好优化。

基本思路

这……“只可意会不可言传”？

把问题分成若干阶段，如 “前 i 个数”；
寻找每个阶段可能的决策，用其向后推理。（数学上描述为状态转移方程）

如果用图论思想理解，每个状态是点，每个决策是边，问题就变成 DAG 上求解最长/最短路的问题了。

实现方式

一般是两种：不限制递推顺序的 记忆化搜索 和更好理解的递推。

下面以 P2602 举例。

递推版本：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int l,r,dp[15],m[15],a[15],a1[15],a2[15];
void work(int n,int *ans){
    int t=n;
    int len=0;
    while(n)a[++len]=n%10,n/=10;
    for(int i=len;i>=1;--i){
        for(int j=0;j<=9;++j)ans[j]+=dp[i-1]*a[i];
        for(int j=0;j<a[i];++j)ans[j]+=m[i-1];
        t-=m[i-1]*a[i],ans[a[i]]+=t+1;
        ans[0]-=m[i-1];
    }
}
signed main(){
    cin>>l>>r;
    m[0]=1ll;
    for(int i=1;i<=13;++i){
        dp[i]=dp[i-1]*10+m[i-1];
        m[i]=m[i-1]*10ll;
    }
    work(r,a1);
    work(l-1,a2);
    for(int i=0;i<=9;++i)cout<<a1[i]-a2[i]<<" ";
    return 0;
}

记忆化搜索版本：(感觉数位 DP 的记忆化搜索更好想，注意别打成暴搜了)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[13][2][2][13],dig[13],key,cnt=0;
int dfs(int pos,bool lim,bool qdl,int sm){
    if(pos==cnt+1)return sm;
    if(dp[pos][lim][qdl][sm]!=-1)return dp[pos][lim][qdl][sm];
    int ans=0;
    for(int i=0;i<=(!lim?9:dig[pos]);++i){
        if(qdl&&!i)ans+=dfs(pos+1,lim&&(i==dig[pos]),1,sm);
        else ans+=dfs(pos+1,lim&&(i==dig[pos]),0,sm+(i==key));
    } 
    dp[pos][lim][qdl][sm]=ans;return ans;
}
int helper(int x){
    memset(dp,-1,sizeof dp);memset(dig,0,sizeof dig);cnt=0;
    while(x)dig[++cnt]=x%10,x/=10;reverse(dig+1,dig+1+cnt);
    return dfs(1,1,1,0);
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    int l,r;cin>>l>>r;
    for(key=0;key<=9;++key)cout<<helper(r)-helper(l-1)<<' ';
    return 0;
}

怎么写记搜

把这道题的 dp 状态和方程写出来，根据它们写出 dfs 函数，添加记忆化数组。

这种方法适用于状态转移方程不复杂（那不如写递推）的时候，如最长上升子序列：

f_i=\max\{f_j\}+1(1 \le j \lt i \text{ 且 }a_j<a_i)

但是这样有的时候有点麻烦。特别是以后 DP 式子有点复杂。那么：

先写暴搜版本，把里面的外部变量清除了，添加记忆化数组。然后 O(2^n) 变 O(n^2)。

背包 DP

0-1 背包

你这肯定不能贪心。递推式显然。 ```cpp #include<bits/stdc++.h> using namespace std; int w[100001],p[100001],f[100001]; int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ cin>>w[i]>>p[i]; } for(int i=1;i<=n;i++){ for(int j=m;j>=w[i];j--){ f[j]=max(f[j],f[j-w[i]]+p[i]); } } cout<<f[m]<<endl; return 0; } ``` ## 完全背包那如果每一组能取无限个呢？ ```cpp #include<bits/stdc++.h> #define int long long using namespace std; int k,n; int f[11451410]={},v[11451410],w[11451410]; signed main(){ ios::sync_with_stdio(false);cin.tie(0),cout.tie(0); cin>>k>>n; for(int i=1;i<=n;++i)cin>>w[i]>>v[i]; for(int i=1;i<=n;++i) for(int j=w[i];j<=k;++j)//正向 f[j]=max(f[j],f[j-w[i]]+v[i]); cout<<f[k]; return 0; } ``` ## 多重背包现在每种选 $k_i$ 个。如果把 $k_i$ 次拆成 $k_i$ 个“选一次”，那么复杂度奔着 $O(W\sum_{i=1}^n k_i)$ 去了，不是很好。考虑到每个数都可以被拆分为最多 $O(\log_2 N)$ 个二进制位，我们把物品拆成若干个二进制位次，时间复杂度立马下到 $O(W\sum_{i=1}^n \log_2 k_i)

当然你可能需要单调队列优化。

混合背包

把那上面三类混到一起。

P1833 樱花

这题的程序里有三种背包的板子。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int h1,h2,m1,m2,n,k;
int v[1145141],w[1145141],f[1145141]={},c[1145141]={},cnt=0;
signed main(){
    scanf("%lld:%lld %lld:%lld%lld",&h1,&m1,&h2,&m2,&n);
    k=(h2-h1)*60+(m2-m1);
    for(int i=1,W,V,C;i<=n;++i){
        cin>>W>>V>>C;
        if(!C)C=114514;
        int x=1;
        while(C>x){
            C-=x;
            v[++cnt]=V*x;
            w[cnt]=W*x;
            x<<=1ll;
        }
        if(C)v[++cnt]=C*V,w[cnt]=C*W;
    }
    for(int i=1;i<=cnt;++i){
        for(int j=k;j>=w[i];--j){
            f[j]=max(f[j],f[j-w[i]]+v[i]);
        }
    }
    cout<<f[k];
    return 0;
}

二维费用背包

你不是已经压掉编号那一维了吗？在开一维存储另一种费用就行。

#include<bits/stdc++.h>
using namespace std;
int dp[501][501];
int s[10001],q[10001];
int n,m,t;
int main(){
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++)cin>>q[i]>>s[i];
    for(int i=1;i<=n;i++){
        for(int j=m;j>=q[i];j--){
            for(int k=t;k>=s[i];k--){
                dp[j][k]=max(dp[j][k],dp[j-q[i]][k-s[i]]+1);
            }
        }
    }
    cout<<dp[m][t];
    return 0;
}

分组背包

把“同组内只选一件”变成“当前组内选一件”。跑 0-1 背包。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int m,n,z=-1,in;
int t[1001][1001]={0};
int w[1000001]={},v[1000001]={},cnt[1000001]={},f[1000001]={};
signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>m>>n;
    for(int i=1;i<=n;++i){
        cin>>w[i]>>v[i]>>in;
        t[in][++cnt[in]]=i;z=max(z,in);
    }
    for(int i=1;i<=z;++i){
        for(int j=m;j>=0;--j){
            for(int k=1;k<=cnt[i];++k){
                if(j>=w[t[i][k]])f[j]=max(f[j],f[j-w[t[i][k]]]+v[t[i][k]]);
            }
        }
    }
    cout<<f[m];
    return 0;
}

有依赖的背包

考虑分类讨论。对于一个主件和它的若干附件，有以下几种可能：只买主件，买主件 + 某些附件。因为这几种可能性只能选一种，所以可以将这看成分组背包。

如果是多叉树的集合，则要先算子节点的集合，最后算父节点的集合。

泛化物品的背包

有的时候物品的价值随着其费用决定。把价值用函数表示即可。

输出方案

直接记录选了什么就行。

方案数

dp_i=\sum(dp_i,dp_{i-c_i})

其中 dp_0=1。

最优方案总数

你对于状态初始设正无穷就可实现没装满不转移。也就是恰好装满的最大价值，同时记录方案数即可。

还有第 k 优解。

区间 DP

f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+v) 之类的。f[l][r] 表示区间 [l,r] 的 DP 结果。

特征：可以把区间结果合并，当然可以相反。可将区间问题改为两两合并形式。合并答案可得全局答案。

处理环：开 2 倍空间（更优）或者枚举断点。

P1880 [NOI1995] 石子合并

#include<bits/stdc++.h>
#define int long long
using namespace std;
int f1[1145][1145],f2[1145][1145],s[1145]={},a[1145],n;
signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    memset(f1,0x3f,sizeof f1);
    memset(f2,-0x3f,sizeof f2);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i],s[i]=s[i-1]+a[i],f1[i][i]=f2[i][i]=0;
    for(int i=n+1;i<=n+n;++i)a[i]=a[i-n],s[i]=s[i-1]+a[i],f1[i][i]=f2[i][i]=0;
    for(int l=2;l<=n*2;++l){
        for(int i=1;i+l-1<=n*2;++i){
            int j=i+l-1;
            for(int k=i;k<j;++k)f1[i][j]=min(f1[i][j],f1[i][k]+f1[k+1][j]+s[j]-s[i-1]),f2[i][j]=max(f2[i][j],f2[i][k]+f2[k+1][j]+s[j]-s[i-1]);
        }
    }
    for(int i=1;i<n;++i)f1[0][0]=min(f1[0][0],f1[i][i-1+n]),f2[0][0]=max(f2[0][0],f2[i][i-1+n]);
    cout<<f1[0][0]<<endl<<f2[0][0];
    return 0;
}

DAG 上 DP

就是把状态变成 DAG 上的点和边，跑 DAG 上最长路/最短路。

树形 DP

就是在树上一边 DFS 一边维护些信息，比如子树大小什么的。

P1352 没有上司的舞会

这人来了她的下属就不来，这人不来她的下属就可来可不来。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int r[N],n,dp[N][2],fa[N],rt;
vector<int>e[N];
inline void dfs(int u){
    dp[u][0]=0,dp[u][1]=r[u];
    for(auto v:e[u]){
        dfs(v);
        dp[u][0]+=max(dp[v][0],dp[v][1]);
        dp[u][1]+=dp[v][0];
    }
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>r[i];
    for(int i=1;i<n;++i){
        int u,v;cin>>u>>v;
        e[v].push_back(u);fa[u]=v;
    }
    for(int i=1;i<=n;++i)if(!fa[i]){rt=i;break;}
    dfs(rt);
    cout<<max(dp[rt][0],dp[rt][1]);
    return 0;
}

换根 DP

树形 DP 中的换根 DP 问题又被称为二次扫描，通常不会指定根结点，并且根结点的变化会对一些值，例如子结点深度和、点权和等产生影响。

通常需要两次 DFS，第一次 DFS 预处理诸如深度，点权和之类的信息，在第二次 DFS 开始运行换根动态规划。一般就是计算变化量。

P3478 [POI2008] STA-Station

不难发现儿子做了父亲的父亲后原本这个儿子的子树深度集体 -1，其余部分深度集体 +1。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
vector<int>g[N];
int dp[N],dep[N],sz[N],f[N];
int n,maxx=LLONG_MIN,ans;
inline void dfs(int x,int ls){
    dep[x]=dep[ls]+1;
    dp[x]=dep[x];
    sz[x]=1;
    for(auto i:g[x]){
        if(i!=ls){
            dfs(i,x);
            dp[x]+=dp[i];sz[x]+=sz[i];
        }
    }
}
inline void ys(int x,int ls){
    for(auto i:g[x]){
        if(i!=ls){
            f[i]=f[x]+n-2*sz[i];
            ys(i,x);
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<n;++i){
        int u,v;cin>>u>>v;
        g[u].push_back(v),g[v].push_back(u);
    }
    dep[0]=-1;
    dfs(1,0);
    f[1]=dp[1];
    ys(1,0);
    for(int i=1;i<=n;++i)if(f[i]>maxx)maxx=f[i],ans=i;
    cout<<ans;
    return 0;
}

状压 DP

状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。

P1879 [USACO06NOV] Corn Fields G

合法的种地方案有点少，先预处理出来。然后保证和上一行不重复即可。

#include<bits/stdc++.h>
using namespace std;
const int N=12+5;
const int mod=1e8;
int a[N][N],dp[N][1<<12],n,m,g[1<<12],f[N],ans=0,cnt=0;
int main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>m>>n;
    for(int i=1;i<=m;++i)for(int j=1;j<=n;++j)cin>>a[i][j],f[i]=(f[i]<<1)+a[i][j];
    for(int i=0;i<(1<<n);++i)if(!(i&(i<<1)))g[++cnt]=i;
    dp[0][1]=1;
    for(int i=1;i<=m;++i){
        for(int j=1;j<=cnt;++j){
            if((f[i]&g[j])==g[j]){
                for(int k=1;k<=cnt;++k){
                    if(!(g[k]&g[j]))dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
                }
            }
        }
    }
    for(int i=1;i<=cnt;++i)ans=(ans+dp[m][i])%mod;
    cout<<ans;
    return 0;
}

数位 DP

详见 之前的文章。

更为厉害的内容

插头 DP
计数 DP（不会数数怎么办）
动态 DP
概率 DP
各种 DP 优化