动态规划学习-基础篇1

某人最近面试连续两天被问了同一道动态规划问题，所以我便想重新学一下动态规划基础并写篇博客记录下（凑着教下这位同学hhh

基础学习

好饭不怕晚，我决定先看视频速通一下基础，这里强推Acwing

参考：

闫氏DP分析法，从此再也不怕DP问题！

背包九讲专题

LeetCode提高班第三期Week1——模拟专题 && 背包问题后三讲

网上的笔记

闫式DP分析法

具体可以看上面的视频去学一下，我这里简单总结一下

这里先举个不太恰当的例子简单说一下dp在做的事情。假设有一个学校，校长让你去查一下这个学校六年级总共多少人，假设有100人的话一个个去数要数100下，但如果按照班级分类的话，只需要知道每个班有多少人然后求和就可以了，比如只有5个班，而这种思想就是dp（看不懂的话请忽略我的胡言乱语hhh）。

而对于一个可以用dp解决的问题，按照闫式DP分析法，一般分为以下几个部分（直接放y总的图）

可以概括为以下步骤

1. 状态表示：如何定义一个式子来表示状态，比如用f[i][j]，并且表示什么状态（这里单独说一下状态表示方法需要平时多整理题型积累，也就是说需要记忆，现场想比较难）
   • 集合：这里的i和j到底定义了什么样的一个集合
   • 属性：要采用什么方式来选取（max/min/count|最大值/最小值/计数）
2. 状态计算：其实就是递推式

这里用几道例题来说明一下这个分析法如何使用

01背包问题

题目链接

先来张y总分析图

现在来详细说明下是如何分析的，套用上面的公式，我们一个个的来看

1. 状态表示：这里我们用f[i][j]来表示状态i和j下的最大价值（经验主义）
   • 集合：这里的i和j到底定义了什么样的一个集合？这里的i代表的是只考虑前i个物品，这里的j表示的是总体积上限为j。综合来说，这里的集合为：所有只考虑前i个物品，且总体积不超过j的选取方法的集合。
   • 属性：要采用什么方式来选取（max/min/count|最大值/最小值/计数）？因为是求最大价值，所以选取方式应该是max
2. 状态计算：假设目前已选好了前i-1个物品，此时考虑第i个物品，就有两种状态，选和不选（也就是图中的所有不选取第i个物品的方法和所有选取第i个物品的方法两个集合），然后分类讨论下会是什么情况。
   • 不选：如果不选的话，新状态剩余体积不会减少，价值也不会增加，所以有f[i][j]=f[i-1][j]
   • 选：这里如果选第i个物品的话，那么一定且最大仅能有一个$$w_i$$的价值增加，也就是说第i个物品的价值增量是定死的，要想让这个状态价值最大只能让前i-1这个状态价值最大，那么也就是取$$f[i-1][j-v_i]$$为考虑前i-1个状态的最大价值，所以该状态下的价值应该为$$f[i-1][j-v_i]+w_i$$

现在的话，我们就已经用一种很朴素的dp思想把这个问题建模完成了，接下来就是代码实现

朴素代码

#include<iostream>

using namespace std;

const int N = 1010;

int v[N], w[N];
int f[N][N];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j] = f[i-1][j]; //更新不选第i个物品的情况
            if(j>=v[i]) f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]); //更新选第i个物品的情况，这里需要考虑空间满足要求
        }
    }
    //可以思考下这里为什么不用遍历找最优值
    cout<<f[n][m]<<endl;
    return 0;
}

空间优化

这里其实可以对代码进行优化，把原本的二维数组变成一维数组，这里把代码主要部分拿出来说一下

for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
		f[i][j] = f[i-1][j];
		if(j>=v[i]) f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);
    }
}

可以看出来每次更新其实只用到了i和i-1这两个状态，所以我们考虑把第一维给它删掉，只用体积来表示状态，而这里优化空间要严格遵循等价原则，做到等价替换，先看不选第i个物品时的情况

f[i][j] = f[i-1][j];  ==>   f[j] = f[j];

这里是可以直接替换掉的，因为不选第i个物品对于状态是没有影响的，所以直接替换掉就好，但是第二个能像下面这样直接替换掉吗？

f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);    =======>    f[j] = max(f[j],f[j-v[i]]+w[i]);

其实在状态选取和转移的时候要遵循一个重要的原则——不重不漏（取大取小有时候重复下对结果没影响），而对于这里的这个变换明显是会对状态有不当的覆盖的。

具体的分析可以看这个笔记和这篇题解（里面有对过程的模拟，还比较细）以及里面的讨论区（讨论区卧虎藏龙呀），这里我简单举例子说明下。对于01背包dp的思路其实是每次都会把i-1这个状态的所有值算出来，然后再提供给i这个状态来更新，如果是二维数组的话是各个状态是完全独立的，相互之间没有什么影响。

但是如果用一维数组来更新的话，每个状态更新其实用的都是这同一个一维数组，那么对于每个较大索引值，在它们被更新前必须保证较小的索引值还没有被更新。而这里对于原本的j:1->m这个循环来说，如果在前面已经算出来了一个合适的$$f[i-1][j-v_i]+w[i]$$的话，就会把较小的$$f[i][j]$$的值更新掉，那么后面较大的$$f[i][j]$$在更新的时候其实就用的前面已经被更新过得值，这样就会导致更新到不正确的值。（我这里符号用的不是太好，可以看我前面说的资料去看具体的模拟例子）

那么如何解决这个问题呢？其实也比较简单，就是改变第二层循环的顺序，从大到小遍历，这样每个状态只会用比自己索引值小的状态的值来更新自己，而比自己索引值小的状态的值都是没被更新过的，完美解决！

#include<iostream>

using namespace std;

const int N = 1010;

int v[N], w[N];
int f[N];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            f[j] = max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

这里我们也可以对比一下两个方法的空间消耗，效果还是比较明显的

完全背包问题

题目链接

看见dp问题别管三七二十一，直接掏出我们的闫式dp分析法！

这里简单解释下

1. 状态表示：这里我们用f[i][j]来表示状态i和j下的最大价值（经验主义）

   • 集合：所有只考虑前i个物品，且总体积不超过j的选取方法的集合。
   • 属性：max

2. 状态计算：假设目前已选好了前i-1个物品，此时考虑第i个物品，就有k+1种状态$${选0个(也就是不选),选1个,选2个,…,选k个}$$，这里选k个的前提是体积不超出界限，然后分类讨论下会是什么情况。

   • 选0个：如果不选的话，新状态剩余体积不会减少，价值也不会增加，所以有f[i][j]=f[i-1][j]

   • 选多个：不失一般性，这里我们直接看选k个这个状态，这里如果选k个第i个物品的话，那么一定且最大仅能有一个$$k \times w_i$$的价值增加，也就是说选k个第i个物品的价值增量是定死的，要想让这个状态价值最大只能让前i-1这个状态价值最大，那么也就是取$$f[i-1][j-k\times v_i]$$为考虑前i-1个状态的最大价值，所以该状态下的价值应该为$$f[i-1][j-k\times v_i]+k\times w_i$$，

   • 综合上面情况来说的话，要使得价值最大，就是从这些状态里选max，也就是
     $$
     f[i][j] = max(f[i-1][j],f[i-1][j-v_i]+w_i,f[i-1][j-2\times v_i]+2\times w_i,…,f[i-1][j-k\times v_i]+k\times w_i,…)
     $$
     这里用$$j-v_i$$去替换$$j$$可以得到
     $$
     f[i][j-v_i] = max(f[i-1][j-v_i],f[i-1][j-2\times v_i]+w_i,f[i-1][j-3\times v_i]+2\times w_i,…,f[i-1][j-(k+1)\times v_i]+k\times w_i,…)
     $$
     可以看出$$f[i][j-v_i]$$也就是后面那么多取值里的最大值（差别只有一个常量$$w_i$$因此加上一个后依然是最大），因此原来的式子可以简化为
     $$
     f[i][j] = max(f[i-1][j],f[i][j-v_i]+w_i)
     $$

很好，分析完毕，进入coding环节！

朴素代码

#include<iostream>

using namespace std;

const int N = 1010;
int v[N],w[N];
int f[N][N];


int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j] = f[i-1][j];
            if(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

空间优化

这里的空间优化比较简单，还是遵循等价原则

f[i][j] = f[i-1][j]; ====>  f[j] = f[j]; //这里是直接成立的，因为取f[j]没被更新过
f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);   ====> f[j]=max(f[j],f[j-v[i]]+w[i]); //这里其实也是成立的，因为这里算f[j]的时候f[j-v[i]]其实已经被更新过了，也就是刚好是f[i][j-v[i]]，刚好是第i层的值，因此也等价

优化后代码如下

#include<iostream>

using namespace std;

const int N = 1010;
int v[N],w[N];
int f[N];


int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=v[i];j<=m;j++){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

石子合并

题目链接

这个题目涉及到一点新的知识，就是这里的dp模型其实是个区间合并模型，但别怕，依然是掏出我们的闫式DP分析法！

这里简单解释下

1. 状态表示：这里我们用f[i][j]来表示状态i和j下的最小代价（经验主义）

   • 集合：所有将区间[i,j]内的石子合并到一起的方法的集合。
   • 属性：min

2. 状态计算：这里可以考虑将[i,j]这个区间分成两个部分，也就是找个地方从中间切开。为了不失一般性，我们假设从k这个地方切开，也就是为为[i,k]和[k+1,j]两个部分（这里要注意保证右半边至少有一堆石子），而这两个部分各自的合并其实是各自独立的，所以只需要计算两部分各自的最小值然后加上整体区间合并的代价即可（这个整体区间的值可以用前缀和计算，前缀和数组用s表示），也就是
   $$
   f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1])
   $$

哟西！分析完毕，进入coding环节！

#include <iostream>

using namespace std;

const int N = 310;

int s[N]; //前缀和数组
int f[N][N];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>s[i],s[i]+=s[i-1];
    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j = i+len-1;
            f[i][j] = 1e8;
            for(int k=i;k<j;k++) f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
        }
    }
    cout<<f[1][n]<<endl; //根据定义就可以知道了
    return 0;
}

最长公共子序列

题目链接

首先，这是个线性DP问题！然后，看到DP想什么！没错！那就是！闫式DP分析法！（好中二。。。。。。）

老规矩y总手绘图镇楼

由于某些原因，这道题我会讲得稍微详细一点（某人好好看好好学hhh）

这里简单解释下

1. 状态表示：这里我们用f[i][j]来表示状态i和j下的最长公共子序列的长度（经验主义）

   • 集合：所有对于字符串A[1~i]和B[1~j]的公共子序列的集合。
   • 属性：max

2. 状态计算：这里对于f[i][j]这个状态，有以下四种选择

   • 同时要A[i]和B[j]：当满足A[i]==B[j]的时候，将这两个字符同时添加进来即可，那么此时最长公共子序列的长度应该是f[i-1][j-1]+1

   • 同时不要A[i]和B[j]：也就是两个序列都没有添加字符进来，其实就还是上一个状态f[i-1][j-1]

   • 要B[j]但不要A[i]：也就是序列B添加一个字符但是A不添加，这里有个直觉思路就是直接用f[i-1][j]来更新即可。但是这里的要B[j]但不要A[i]指的是B一定要添加一个字符而A不添加，而f[i-1][j]其实并不代表B序列里面一定有B[j]这个字符，并且，其实并没有一个很好的办法可以完美的表示这种状态。这里考虑最大最小本身的特性，举个例子，对abc三个数字求最大值，有一种方案是先对ab求最大值得d，再对bc求最大值得e，然后对de求最大值，在这个步骤里，b被重复使用了，但是并不会影响结果。回到这个问题本身来，即便是f[i-1][j]并不可以完美表示这个状态，但他一定是包含这个状态的，并且由于求得是最大值，因此对结果并没有影响，所以状态表示为f[i-1][j]

   • 要A[i]但不要B[j]：原理同上一个状态，状态表示为f[i][j-1]

   • 然后综合上面四个情况再来看一下，其实第2个情况很明显是包含在第3种和第4种情况里面的，所以可以直接舍去，因此最后的状态转移方程可以写为
     $$
     f[i][j] = min(f[i-1][j],f[i][j-1],f[i-1][j-1]+1)
     $$

代码环节！

#include<iostream>

using namespace std;

const int N = 1010;

char a[N],b[N];
int f[N][N];

int main(){
    int n,m;
    cin>>n>>m>>a+1>>b+1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j] = max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j]) f[i][j] = max(f[i][j],f[i-1][j-1]+1);
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

总结

简单复习了下以前学习的dp方面的一些基础知识（想起了以前打算法的青葱岁月呢~），主要是介绍了面对一个dp问题时如何使用闫式DP分析法来对问题进行一个较为直观的建模进而解决问题。

后续的话应该就是多搜集一些基础模型加进来，比如背包九讲（熟悉的味道，回来了！）、数位dp、状态压缩dp以及树形dp等了，先咕咕一阵子。