动态规划入门笔记

Ginreny · 2020-04-03 19:19:42 · 个人记录

动态规划，也称为DP，是求解决策过程最优化的数学方法。
20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，
提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，
利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划

上面废话这么多，那么动态规划到底是个什么呢？

是一种能帮助我们得分的方法

第一次直接理解是不可能的，接下来就用题目来理解吧QwQ

前置芝士：dfs，建图，拓扑排序

目录

    1.数字三角形 记搜

    2.LIS 线性DP

    3.01背包和完全背包 线性DP

    4.路径搜寻问题 二维DP

    5.USACO 248G 区间DP

    6.石子合并 环形区间DP

    施工中ing...

1.数字三角形

题目链接：P1216

相信在学习动态规划之前，我们第一个想到的方法就是大法师DFS，我们枚举遍历每一条路径，从中选取 max 值

思路很简单，但是只要尝试就会发现一堆TLE

那怎么办呢？我们看一看我们的思路上有什么可以优化的地方吧

在枚举每一条路径时，我们发现同一个节点被遍历了许多次，那么，我们就对节点做文章，我们先开一个数组 f[i][j] ，记为第 i 行第 j 列的节点从顶端至自己所能取到的最大的路径之和

那么如何求这个路径和呢，想想之前写的程序，我们对从最顶端的节点下来的路径判断其大小，那么，我们可以先遍历各个节点，在各个节点进行回溯

接下来便是最重要的步骤了，我们既然已经知道了在当前节点左下方与右下方的节点中所能遍历到的最大子树大小，所以在当前节点时，我们只需要选择左下与右下两节点中较大的一个作为所选路径，于是 f[i][j] 便可如此得出:

这个递推方程看齐来很长，但仔细观察便可发现其核心在于由上面的节点得出该节点答案，在 j=1 时，我们只能遍历左节点

我们需要先遍历下面的节点后遍历上面的节点，通过 ans 记录我们所需的答案，我们将我们的dfs改一下：

void dfs(int x,int y)
{
    if(f[x][y])
    {
        return;
    }
    if(x==1)
    {
        f[x][y]=a[x][y];
        return;
    }
    if(y==1)
    {
        dfs(x-1,y);
        f[x][y]=a[x][y]+f[x-1][y];
    }
    else if(j>1 and j<n)
    {
        dfs(x-1,y);
        dfs(x-1,y+1);
        f[x][y]=max(f[x-1][y],f[x-1][y-1])+a[x][y];
    }
    else
    {
        dfs(x-1,y+1);
        f[x][y]=a[x][y]+f[x-1][y-1];
    }
}

如果是第一次接触DP,这一个递推公式可能有点难以理解一眼看不懂再看一眼，但实际上我们在DP的过程中，一般而言，有如下几个方法：

• DP什么就令数组中存什么
• 我们可以通过先写出DFS程序再对其中结果存储
• 再考虑DP方程时，我们可以假设之前状态已经是最优了（例如上题中 f[x+1][y] 和 f[x+1][y+1])
• 考虑一下当前状态与之前什么状态有关

当然，这并不是通性通法，但是可以在帮助我们学DP的过程中理清我们的方向

其实大多数DP并不用dfs，我们现在考虑一下，对于下一排的程序，只要我们知道了上一排，便可由递归得出，所以我们只需要从下到上遍历这个数字三角形，最后就能得到答案

所以这个程序还可以这么写：

    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            if(j==1)
            {
                f[i][j]=a[i][j]+f[i-1][j];
            }
            else if(j>1 and j<n)
            {
                f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
            }
            else
            {
                f[i][j]=a[i][j]+f[i-1][j-1];
            }
            ans=max(ans,f[i][j]);
        }
    }
    printf("%d",ans);

相比于dfs,这个程序有什么好处呢？因为dfs中函数递归需要时间消耗，所以可能导致程序TLE，但是DFS写的程序可以直接改为DP，所以相较于循环，Ta的思路简单一些吧

2.最长上升子序列(LIS)

题目链接：AT2827

对于这一题，首先我们想一想暴搜的思路

枚举节点，再判断其是否还能延续（在后面有没有比Ta大的节点），然后判断其是否大于已知的最长长度，如果是，记录其长度

想都不用想肯定TLE

最好的办法是采用DP的思路，结合上面的DP方法试一试

1. DP什么就令数组存什么：存储在当前节点之前能达到的最长子串

2. 写出DFS程序：太懒了不想写

3. 假设子状态已经是最优了：如果我们当前节点遍历到 i ,那么 f[j]\quad(0<j<i) 里存储的都是在第 j 个节点中达到的最长序列大小

4. 考虑一下当前状态与之前什么状态有关：当且仅当这个节点的值比之前节点大时，这个序列才能延续下去，并且长度加一

所以我们能得出这个递推方程：

看起来很简单

所以我们只需用 ans 记录一下最大值即可

代码如下：

#include<iostream>
#include<cstdio>
#define MAX 10005
using namespace std;
int a[MAX],f[MAX],n,ans;//当数组开在主函数外面时，默认初值为0，保证最小
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i])
            {
                f[i]=max(f[i],f[j]+1);//DP方程
            }
        }
        ans=max(ans,f[i]);//储存最大值
    }
    printf("%d",ans);
}

当然，我们一看到代码中的两个循环，再一看数据中的10^5,很明显，我们 O(n^2) 的算法达不到题目所需的 O(nlogn) 要求，那怎么办呢？

我们就需要贪心了(原来DP不万能 不学DP了)

我们可以采用二分+贪心的思想，因为当结尾数字越小时，更能得到最长的方程

由于不像DP思路，就不上代码了 其实就是不会

在这道题目中，我们考虑了当前节点和之前节点的关系，作为线性DP中最基础的部分，让我们在学习Ta之后继续前进吧

相关习题：

1.P1091 合唱队形

2.P1020 导弹拦截

3.01背包和完全背包

题目链接: P1048 01背包

完全背包裸题找不到QwQ

作为DP中的重头戏，背包问题是永远躲不过的一个点

01背包可以简化成这样：存在n个物品，其中每个物品都有各自的重量 w[i] 和价值 v[i] ，每个物品只能取一次，我们需要在不超过 weight 的质量里达到尽可能多的价值

而完全背包是这样：存在n个物品，其中每个物品都有各自的重量 w[i] 和价值 v[i] ,每个物品能取无限次，我们需要在不超过 weight 的质量里达到尽可能多的价值

先来解决01背包吧

首先我们自然而然想到的是暴力枚举子集，用 0,1 分别表示这件物品是否取，判断总重不超过 weight 后对其最大值记录

思路就是这么简单，但是一想到这 O(n2^n) 的复杂度就显然过不了

好了，接下来我们用DP的思路套一下这道题：

1. DP什么就令数组存什么：这道题中存在两个变量： v[i],w[i] 所以我们可以开一个二维数组 f[i][j] 表示在选取第 i 件物品且背包容量为 j 时所能装载的最大价值

2. 写出DFS程序：这道题dfs程序好像和DP无关就不写了

3. 假设子状态已经是最优了：我们当前节点为 f[x][y] 那么对于 f[i][j]\quad(0<i<x) 里面存储的都是最优值

4. 考虑一下当前状态与之前什么状态有关： 我们用背包装物体的质量，当背包已装物品总数为 i 且质量为 j 时，我们在装进质量为 w 的物体后，背包能装进的质量为 j-w，此时我们又多装了一个物品，所以 f[i][j] 与 f[i-1][j-w] 有关

然后呢？

轻而易举得到了DP方程：

所以我们可以愉愉快快的写出这样的程序：

#include<iostream>//好久以前写的巨丑代码
using namespace std;
int t,m,a[101],b[101],f[101][1001]={0},i,j;
int main()
{
    cin>>t>>m;
    for(i=1;i<=m;i++)
    {
        cin>>a[i];//质量
        cin>>b[i];//价值
    }
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=t;j++)
        {
            if(j>=a[i])//保证背包装的下
            {
                f[i][j]=max(f[i][j],f[i-1][j-a[i]]+b[i]);
            }
        }
    }
    cout<<f[m][t];
}

当然，只要我们尝试交一下，只会听取WA声一片，那么问题到底在哪？

看一下第二层循环

    for(int j=1;j<=t;j++)

我们将 j 从小到大枚举了 好像没什么问题？

思考一下，当我们从小到大枚举容量时，如果我们已经在 f[i][j-w[i]] 放了这件物品，当在 f[i][j] 时，如果DP方程得出结论为我们此时再放这个物品能保证最优，我们对一个物品是不是放了多次？

然而我们并不能将一个物品放置多次，那怎么办呢？

有一个方法，改变枚举 j 的顺序

如果我们从大到小枚举 j 那么就能保证在 j 之前没有放，因为前面还没有遍历到，所以不可能放该物品

好像有些难以理解，那就上一张图:

在上图中，我们假设只有一个物品，那么从小到大遍历 j 就会使子状态先于当前状态改变，也就会发生 f[1][8]=4 这样这样不可能的答案

所以我们改一下遍历方式，子状态不能先于当前状态改变，也就保证了每个物体只取一次，所以得出正确答案：f[1][8]=1

程序就改成这样了：

#include<iostream>
using namespace std;
int t,m,a[101],b[101],f[101][1001]={0},i,j;
int main()
{
    cin>>t>>m;
    for(i=1;i<=m;i++)
    {
        cin>>a[i];//质量
        cin>>b[i];//价值
    }
    for(i=1;i<=m;i++)
    {
        for(j=t;j>=0;j--)//这里改了
        {
            if(j>=a[i])//保证背包装的下
            {
                f[i][j]=max(f[i][j],f[i-1][j-a[i]]+b[i]);
            }
        }
    }
    cout<<f[m][t];
}

那么刚开始的程序没用了吗？这不至于，每个物品可以放无限次，那么不就是完全背包？

所以在这里请注意，对DP方程的遍历方式也很重要！！！

当然，在看了许多大佬的代码之后，我们会发现，他们并不使用二维数组，相反，一维数组竟然也能解决这个问题

我们不用关心去放几个物品了，我们直接考虑当前背包中所拥有的物品质量大小， 我们可以直接设 f[i] 表示为当背包容量为 i 时，背包所能承载的最大价值， 那么，我们根据上面的DP方程，也能得出一个方程：

看起来这个方程没什么区别

对于数据过大可导致的MLE，Ta极大地减少了空间复杂度，就非常优秀

那么，是不是什么DP方程都能用这样的方法呢？

其实不然，像上面的方程中， f[i][j] 只与 f[i-1][x]\quad (0<x<j) 有关，当且仅当此时，我们可以用滚动数组优化，将二维的DP化为一维DP（这方法叫滚动数组）

所以这道题代码可以这么写：

01背包：

#include<iostream>
using namespace std;
int main()
{
    int t,m,a[101],b[101],f[1001]={0},i,j;
    cin>>t>>m;
    for(i=1;i<=m;i++)
    {
        cin>>a[i];
        cin>>b[i];
    }
    for(i=1;i<=m;i++)
    {
        for(j=t;j>=0;j--)
        {
            if(j>=a[i])
            {
                f[j]=max(f[j],f[j-a[i]]+b[i]);
            }
        }
    }
    cout<<f[t];
}

完全背包：

#include<iostream>
using namespace std;
int main()
{
    int t,m,a[101],b[101],f[1001]={0},i,j;
    cin>>t>>m;
    for(i=1;i<=m;i++)
    {
        cin>>a[i];
        cin>>b[i];
    }
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=t;j++)
        {
            if(j>=a[i])
            {
                f[j]=max(f[j],f[j-a[i]]+b[i]);
            }
        }
    }
    cout<<f[t];
}

当然，背包的种类还有好多种，在这里就不一一讲述了，详情请百度背包九讲

相关习题:

1.P1048 采药

2.P1616 疯狂的采药

3.1049 装箱问题

4.路径搜寻问题

题目链接：最低通行费

对于这道题，由于我们只能走 2n-1 步，所以我们每次只能往下或右走,这样一看就与数字三角形差不多，我们设当前节点的最小通行费为 f[i][j],我们可以根据第一题，得出这个方程：

当然我们需要对边界特判一下，以免导致越界

所以程序可以这么写：

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
    long long a[101][101],f[101][101],n;
    memset(a,0,sizeof(a));
    memset(f,0x3f3f3f,sizeof(f));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=n;j>=1;j--)
        {
            if(i==n and j==n)
            {
                f[i][j]=a[i][j];
        }
            else if(i==n and j!=n)
            {
                f[i][j]=f[i][j+1]+a[i][j];
            }
            else if(i!=n and j==n)
            {
                f[i][j]=f[i+1][j]+a[i][j];
            }
            else(i!=n and j!=n)
            {
                f[i][j]=a[i][j]+min(f[i][j-1],f[i-1][j]);
            }
        }
    }
    printf("%d",f[1][1]);
}

结束了？ 结束了

题目当然简单，但是如果我们把走路次数改为无限次(也就是可以向四个方向走)，并将节点的值范围扩大到负数呢？

在有了上面经验后，我们又可以很简单的写出这样一个方程：

看起来很正确？

然而事实表示Ta并不正确

问题在哪？我们假设已经DP至 f[i][j] ，那么我们通过其中任意节点改变了该节点的值，考虑一下我们之前遍历过的 f[i-1][j] ，Ta的值是不是要更改了？

所以DP得不出正确答案

在这里我们对DP又发现了一个新要求，及某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响，说的简单点，就是在改变父状态后，其子状态都不能再改变，再说简单点，就是"未来与过去无关"(来源百度)

这个要求也被称为无后效性，所有的DP都必须保证无后效性

所以，在以后的题目中，我们必须仔细判断一道题是否具有无后效性再考虑DP，不然在考场中，不但存在爆0的可能性，更会因检查消耗大量时间，就很亏

5.USACO 248G

题目链接：P3146

这看起来也是一个线性区间？

那就按照之前的方法试一试：

1. DP什么就令数组存什么：存储在当前节点之前能达到的最大和

2. 写出DFS程序：还是太懒了不想写

3. 假设子状态已经是最优了：如果我们当前节点遍历到 i ,那么 f[j]\quad(0<j<i) 里存储的都是在第 j 个节点中达到的最大和

4. 考虑一下当前状态与之前什么状态有关：当且仅当两节点大小相同时，它们才可以合并

但是这个在合并之后会改变原来的数值呀

所以也就表明这题不是这样的思路QwQ

我们可以从题目中的操作得知，该操作仅将两个数字合并为一个，那么这个数字的表示方法就成了题目的关键

我门在最后需要在这一个区间中得到值，既然对每一位DP不行，那么是否可以尝试对每个区间DP呢？

假定我们有 n 个数字，那么我们将此区间定义为 [1,n], 表示从第一个数字到第 n 个数字的区间，我们通过数组 f[1][n] 表示这个区间

我们知道,一个大区间是由两个子区间合并而来的，由题目易得，这两个区间不能相交，且这两个区间合并后必须为大区间

正如上图所示，只有这样的两个黄蓝区间才可满足转移，而中间的分隔线可以随意移动，这个分隔线是影响大区间值的唯一元素

所以我们在转移状态的过程中，只需枚举这个分隔线的位置即可

我们设 i,j 分别为该区间 的左右端点， k 为该区间的分隔线位置，然后我们便有了如下状态转移方程：

由于题目要求两数相同时才可合并，所以有了 f[i][k]=f[k+1][j] 这个要求

接下来给出代码：

#include<iostream>
#include<cstdio>
#define MAX 255
using namespace std;
int f[MAX][MAX],n,ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&f[i][i]);
        ans=max(ans,f[i][i]);
    }
    for(int len=1;len<=n;len++)//循环1
    {
        for(int i=1,j=i+len;j<=n;i++,j++)//循环2
        {
            for(int k=i;k<j;k++)//循环3
            {
                if(f[i][k]==f[k+1][j])
                {
                    f[i][j]=max(f[i][j],f[i][k]+1);
                    ans=max(ans,f[i][j]);
                }
            }
        }
    }
    printf("%d",ans);
}

正如同上面代码所给出的，在第一个循环中，我们枚举所要合并的大区间的长度，并通过第二个循环设定这个区间的边界，在第三个循环里，我们枚举的是这个区间合并的位置，并判断大区间的两部分是否可被合并，最后，我们通过 ans 记录答案

6.石子合并

题目链接：石子合并

好像和上题差不多？

由上题，我们易得如下DP方程：

其中 f[i][j] 表示以 i 为开头，j 为结尾的区间合并后所能得到的最大值， g[i][j] 表示最小值

但是仔细一看，石子形成里一个环

通过我们以往的经验可得，我们可以枚举断开此环的位置

但是复杂度会变为 O(n^4) ，显然超过了题目要求范围

怎么办？我们可以将一个环拼接成两个子串，然后再其长度为原环的子串中获取答案即可

当然，光说无意，还是几张图比较好

正如上图，对于这样的一个字符环

我们可以把它转化为如上图的字符串（将两环拼接）

然后我们只需对其长度为5的子串中获取答案即可

开始愉快地写代码：

#include<iostream>  
#include<cstdio>  
#include<cmath>
#define Max 0x3f3f3f3f
using namespace std;   
int n,minl,maxl,f1[Max][Max];
int f2[Max][Max],num[Max];  
int s[Max];  
inline int d(int i,int j)
{
    return s[j]-s[i-1];
}  
int main()  
{   
    scanf("%d",&n);  
    for(int i=1;i<=n+n;i++)//将两个环连接
    {  
        scanf("%d",&num[i]);  
        num[i+n]=num[i];  
        s[i]=s[i-1]+num[i];  
    }  
    for(int p=1;p<n;p++)  
    {  
        for(int i=1,j=i+p;(j<n+n) && (i<n+n);i++,j=i+p)  
        {  
            f2[i][j]=Maxa;  
            for(int k=i;k<j;k++)  
            {  
                f1[i][j] = max(f1[i][j], f1[i][k]+f1[k+1][j]+d(i,j));   
                f2[i][j] = min(f2[i][j], f2[i][k]+f2[k+1][j]+d(i,j));  
            }  
        }  
    }  
    minl=Maxa;  
    for(int i=1;i<=n;i++)  
    {  
        maxl=max(maxl,f1[i][i+n-1]);//只对区间长度为n的子串获取答案  
        minl=min(minl,f2[i][i+n-1]);  
    }  
    printf("%d\n%d",minl,maxl);  
    return 0;  
}

所以我们在看过这两道区间DP题后，我们可以观察到区间DP题目的一些规律：

一般而言，当我们看到合并问题时，我们可以考虑区间DP

并且，区间DP的设置一般为区间两端点，通过DP得到最值

一个普遍的区间DP方程：

其中 w[i] 表示区间合并的代价