动态规划总结 【分类1-基础模型】

· · 闲话

动态规划总结 【分类1-基础模型】

1.线性DP

1.1 综述

线性动态规划问题，就是说每个子问题的阶段以线性方式递推的动态规划问题。

这种问题是动态规划的基础。一般来说，如果不是对状态表示层面开展优化，那么大多数问题都是线性动态规划，故这就成了最基本的动态规划问题。

2.背包DP

好，这个内容已经写过一次了，现在复制过来并进行了改进

1.01背包

所以你应该想到，这个问题有变量与答案相关：价值，有变量与限制相关：物品体积、背包；有变量与此无关，可以选择作为阶段的变量：物品数

这样应该就清楚了。读者应该已经知道方程是什么了。

优化空间复杂度

方法你应该已知，要注意的是，如果不使用倒序循环，就会出现第i阶段向第i阶段转移的问题，这会导致重复考虑物品。

2.完全背包

假如我们允许从第i个已经考虑物品i的阶段转移到自己，那么就相当于允许放无限物品i。

这仍然满足了“无后效性”的要求，因为在阶段内还是有序从已经计算转移到还没有计算的。

3.多重背包

这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略 微一改即可。只要把物品直接拆分成Mi件就好，实现上只要加一重循环。

以上是书上说的。笔者实际上在写稿的时候发现一件好玩并且有教育意义的事。

代码1：

#include<bits/stdc++.h>
using namespace std;
const int N=10000;
int f[N],c[N],v[N],w[N],n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i]>>c[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=0;j--){
            for(int k=0;k<=c[i]&&k*w[i]<=j;k++){
                f[j]=max(f[j],f[j-k*w[i]]+k*v[i]);
            }
        }
    }
    cout<<f[m];
    return 0;
}

代码2：

#include<bits/stdc++.h>
using namespace std;
const int N=10000;
int f[N],c[N],v[N],w[N],n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i]>>c[i];
    }
    memset(f,0xcf,sizeof f);
    f[0]=0;
    for(int i=1;i<=n;i++){
        for(int k=1;k<=c[i];k++){
            for(int j=m;j>=w[i];j--){
                f[j]=max(f[j],f[j-w[i]]+v[i]);
            }
        }
    }
    int ans=0;
    for(int i=0;i<=m;i++) ans=max(ans,f[i]);
    cout<<ans;
    return 0;
}

这两个代码都能通过AcWing上的模板题。但是仔细看看这两个有多少不同呢。

请注意整个程序从初始化到输出答案都是动态规划的组成部分，请不要漏掉其中一些。

好吧上面那个是我看了书上代码突发奇想又写的。下面那个是书上的。

其实这两份代码有很重要的区别：他们的状态设计甚至不同。

上面那份：f[i]代表容量为i的背包可以获得最多多大的价值？

下面那份：f[i]代表已经装填了i的背包最大价值是多少？

那么，如果是下面那样设计，ok，但是这就要修改一些地方：

所以说，写DP，一定要先根据题目里相关变量确定状态表示，务必扣合，否则就会出现错误

优化

关于拆分，我们隔壁树状数组这个给我们做了一个很好的示范。

但是，如果有一个物体，我们必须把它拆出1,2,3...,Ci个才行。

所以我们知道，这些数一个一个都是可以由某些二的次幂构成的。

但是我们要保证不漏和不超范围，就只能找到这样一个数，使得：

#### 4.分组背包 这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件 都不选。 也就是说，依次看看每一组中的物品是否加入。 ## 3. 区间DP ### 3.1 综述 区间DP求解跟区间有关的动态规划问题。通常来说，这类问题要满足区间可加性，就是要容易从两个子区间合并，这跟线段树的要求是一样的。 ## 4.树形DP ## 4.1 综述 树形DP在树形结构上求解关于：子树、路径之类的问题。还有一些问题利用树形结构表达依赖等关系。 前面已经提到动态规划的转移图形，这里就更加特殊，变成了一棵树。我们可以选择从上自下更新，也可以自下而上转移。 ##### 4.2 有依赖的树形背包 转化为分组背包求解。不再赘述。 ##### 4.3 二次扫描与换根法 很多时候，题目没有给定树形的根，那么，我们难道就必须对于每个树根进行DP了吗？ 注意到实际上对于每一个节点，从这个节点出发必然可以遍历整个状态空间。如果树根对答案来说很重要，那么当然是因为子问题中涉及到子树相关的内容（关心形状），那么经过一次计算，我们实际上可算出所有的点在这个根的情况下的子树里的答案，这些答案就被浪费了，造成冗余的计算。 二次扫描与换根法就是建立在这样的发现上，普遍地说： - 先进行第一次DP，从任意一个根x出发，求出$f_x[i]$代表以x为根时子树i的答案 - 再进行一次扫描，从根x出发，求出$D[i]$代表以i为根的答案，就是用父亲已经算出的答案和第一次算的答案合并 ## 5 计数DP ### 5.1 综述 计数DP，是用来求解计数类问题的动态规划。所以说，要求做到“不重不漏”。 一般情况下，我们求解这类问题，就是同时应用加法原理和乘法原理。 ![](https://cdn.luogu.com.cn/upload/image_hosting/nxzoz0if.png) 如图，比如说f[x]代表达到状态x的方案数，那么$f[E]=f[C]\times ways(C \to E)+f[B] \times ways(B \to E)$这是利用加法原理和乘法原理。 在大多数情况下，DP都能完整地遍历状态空间，我们这类主要考虑如何避免重复以及高效计算。总结来说，就是要考虑每一个方案如果不一样，那么有什么一定不同。这种思想在下面的例题中还可窥见一二。 ## 6 数位DP ### 6.1 综述 数位DP，就是要统计满足某些条件的数字。我们很容易用动态规划预处理出一些信息，然后利用这些信息拼凑答案。