动态规划代码模板

发表于 更新于 分类于 阅读次数：

这里记录了动态规划方面平时个人常用的代码模板。

动态规划

完全背包

$n$种物品，每种有体积$c_i$和价值$w_i$，数量无限。求容量为$V$的背包能装进物品的最大价值。

复杂度$O(nV)$

1
2
3
for(int i=1;i<=n;i++)//n种物品
    for(int j=cost[i];j<=V;j++)//背包容量
        f[j]=max(f[j],f[v-cost[i]]+value[i]);

复杂度$O(V\sum\frac{V}{cost[i]})$

1
2
3
4
for i←1 to n
    for v←0 to V
        for k←0 to v/cost[i]
            f[i][v]=max{f[i-1][v-k*cost[i]]+k*value[i]}

nlogn求LIS

注意：存储的并不是$lis$，需要确定元素，换做$upper_bound()-begin()$即可得到最长非降子序列长度。

还可以按照权值排序，使用树状数组查询区间$[1,id]$最值，。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int lis(int a[],int n)
{
    vector<int>dp(n+1,0);
    int top=0;
    dp[++top]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(dp[top]<a[i])//严格递增
            dp[++top]=a[i];
        else{
            *lower_bound(dp.begin()+1,dp.begin()+top+1,a[i])=a[i];
        }
    }
    return top;
}

狄尔沃斯定理

把一个数列划分成最少的最长不升子序列的数目就等于这个数列的最长上升子序列的长度（LIS)。

区间dp

$$
dp[l][r]=min{dp[l][k]+dp[k+1][r]+cost(l,r)}
$$

$cost(l,r)$为合并区间$[l,k]$与$[k+1,r]$的贡献。

第一维枚举长度$len$，第二维枚举起点$l$，右端点$r$即可由$l+len-1$求得，第三维枚举间断点$k$。

例题

一个数列，你可以一次消掉其中一个回文子段，剩下的元素会自动拼接起来，请问消掉该数列的最小次数。

令$dp[l][r]$表示区间$[l,r]$所消耗的次数。当$a[l]=a[r]$时，$dp[l][r]$可以由$dp[l+1][r-1]$转移而来，因为将$[l+1,r-1]$区间内的回文串消耗至只剩一个时，$a[l]$与$a[r]$拼接至两端仍为回文串，不会增加贡献。之后再枚举分割点$k$，尝试将$[l,r]$分割为$[l,k]$与$[k+1,r]$两部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int a[maxn],dp[maxn][maxn],n;
signed main(signed argc, char const *argv[])
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    memset(dp,inf,sizeof(dp));
    for(int len=1;len<=n;len++)
    {
        for(int l=1;l<=n-len+1;l++)
        {
            int r=l+len-1;
            if(a[l]==a[r])
            {//
                if(r-l<=1)
                    dp[l][r]=1;
                else
                    dp[l][r]=dp[l+1][r-1];
            }
             for(int k=l;k<=r;k++)
                 dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
        }
    }
    cout<<dp[1][n]<<endl;
    return 0;
}
/*
6
1 2 1 1 3 1
*/
/*
 * 2021-04-11-19.33.55
 * abbbdbb aca ba
 * 令dp[l][r]为消掉[l,r]区间的最小次数
 * 若a[l]=a[r],则dp[l][r]可以=dp[l+1][r-1]但不一定最优
 * 仍需要枚举分割点
 * 否则只能将子段分割
*/

状压dp

枚举子集

1
for(int i = all; i; i = (i - 1) & all) { ... }

dp优化技巧

https://www.cnblogs.com/NaVi-Awson/p/12240616.html

https://www.cnblogs.com/flashhu/p/9480669.html

前缀和优化

当转移方程出现$f_i=\sum\limits_{j=l}^{r}g_j$时，对$g$做一个前缀和可以优化掉一维。

P2513 [HAOI2009]逆序对数列

题意：询问长度为$n$的排列逆序对为$m$的数列个数，$1\le n,m\le 10^3$。

定义$dp[i][j]$状态表示为长度为$i$的排列逆序对数为$j$时合法排列数。

当排列长度为$i$时，考虑向原来长度为$i-1$的数列插入元素$i$，一共有$i$个位置可以插，当元素$i$插在第$j$个位置时，会新产生$i-j$个逆序对。可以得到一个我为人人式的转移如下。

1
2
3
4
for(int i=1;i<=n;i++)
    for(int j=0;j<=m&&j<=(i-1)*(i-2)/2;j++)
        for(int k=0;k<=i-1;k++)
            dp[i][j+i-k]+=dp[i-1][j];

稍微转化一下可以得到一个人人为我式的转移，长度为$n$的排列逆序对数目最多为$\dfrac{n\times(n-1)}{2}$。

1
2
3
4
5
dp[0][0]=1;
for(int i=1;i<=n;i++)
    for(int j=0;j<=m&&j<=i*(i-1)/2;j++)
        for(int k=max(0,j-i+1);k<=j;k++)
            dp[i][j]+=dp[i-1][k],dp[i][j]%=mod;

可以发现第三维可以通过前缀和进行$O(1)$转移，可得代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int dp[maxn][maxn],sum[maxn][maxn];
signed main(signed argc, char const *argv[])
{
    int n,m;
    cin>>n>>m;
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=sum[i][0]=1;
        for(int j=1;j<=m;j++)
        {
            if(j<=i*(i-1)/2)
            {
                dp[i][j]=sum[i-1][j];
                if(j-i+1>0)//从j-i+1开始记录答案
                    dp[i][j]-=sum[i-1][j-i];
                dp[i][j]=(dp[i][j]+mod)%mod;
            }
            sum[i][j]=sum[i][j-1]+dp[i][j];
            sum[i][j]%=mod;
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}