简单动态规划

简单动态规划

0 在阅读之前

前备知识可阅读递归与递推

1 基础知识

1.1 介绍

动态规划是运筹学的一个分支,是求解决策过程最优化的数学方法。动态规划不是算法,是一种思想。这种思想把大问题转化为小问题,用小问题的解推断出大问题的解

1.2 例子

  • 问题一:有$n$级台阶,一开始站在0级,每次可以向上走1级或2级,问走到n级的方案总数?

暴力的思想是从0级模拟一直到n级,每次都有两种选择,这种做法的复杂度是指数级的。

有没有一种更好的思想?创建一个数组$f$,以$f[n]$表示从0级到n级的方案数,如果$f[1],f[2],...,f[n-1]$都知道的话,怎么推出$f[n]$?

可以看出,走到当前台阶要么是前一个台阶,要么是前两个台阶,而前一个台阶或前两个台阶又是可以看作当前台阶,所以可以得到递推式:

$$ f[n]=f[n-1]+f[n-2](n \geq 3) $$

其中初始条件是$f[1]=1,f[2]=2$

  • 问题二:你手上有无限多的1,5,11元硬币,给定一个数字$n(n \geq 1)$,问凑出n元需要最少多少枚硬币?

最直接可能想到贪心,也就是每次都找能用的最大面额,但是在$n=15$时遇到了错误,如果是贪心,$11+1+1+1+1$一共是5枚,而$5+5+5$却只需要三枚,所以不能这么做。

我们可以类比问题一的思想:创建一个数组$f$,以$f[n]$表示凑出n元的最小方案数,如果$f[1],f[2],...,f[n-1]$都知道的话,怎么推出$f[n]$?

可以看出,本题有三个选择方案,所以,如果要求方案数最小,那么就选择这三个方案数里面最优的,用式子表达如下:

$$ f[n]=min\left\{\begin{matrix} 1+f[n-1]\\ 1+f[n-5]\\ 1+f[n-11] \end{matrix}\right. $$

其中初始条件是$f[0]=0$

1.3 状态

上面的两个问题我们用了“把大问题转化为小问题,用小问题的解推断出大问题的解”的思想来做,为什么可以这样做呢?这是因为大问题和小问题都有一样的形式

  • 问题一

    • 大问题:走到n级有多少种方案
    • 小问题:走到n-1级有多少种方案,走到n-2级有多少方案
    • 它们都是“走到[...]级有多种方案”
  • 问题二

    • 大问题:凑出n元硬币的最小方案数
    • 小问题:凑出n-1元硬币的最小方案数,凑出n-5元硬币的最小方案数,凑出n-11元硬币的最小方案数
    • 它们都是“凑出[...]元硬币的方案数”

只有大问题和小问题拥有相同的形式,才可以用动态规划这种思想。题目如果满足这个要求,我们遇到每个问题都可以很简洁的表达,这些可能遇到的“局面”称之为状态

设计完状态后,只要能利用小状态的解求出大状态的解,就可以求解题目。

1.4 LIS问题

数组的最长上升子序列是指最长的那一个单调上升的子序列。例如一个数组[1,3,7,4,6,9],它的最长上升子序列是[1,3,4,6,9]。

如果要用动态规划的思想来做,需要先设计状态。如何设计状态?(设数组为a,求解数组为f)

  • 状态:以$a[x]$为结尾的上升子序列最长有多长

用$f[x]$来表示状态的解,那么答案就是$f[1]$到$f[n]$中最大的一个。可以很明显看出,最长的上升子序列一定是插在某个上升子序列的尾部得到的。

考虑上面给出的数组,求f[5]的过程是这样的:

  1. 自己作为一个子序列,值为$1$
  2. 接在$a[1]$后面,值为$f[1]+1$
  3. 接在$a[2]$后面,值为$f[2]+1$
  4. 接在$a[4]$后面,值为$f[4]+1$

看到这里应该可以知道,要求出$f[x]$,只需要知道$a[x]$能接到哪些数的后面,所以我们可以得到式子:

$$ f[x]=max\left \{ f[p]+1 \right \}(p<x,a[p]<a[x]) $$

其中初始条件是$f[1]=1$

1.5 转移

在前面的三个问题中,先是设计好了状态,再给出了由小状态求大状态的方法。从一个状态的解得到另一个状态的解称为“状态转移”,状态转移的式子称为“状态转移方程”。

在设计转移的时候,考虑的都是“这个局面是从哪过来的”,这是转移的一种思路:当前状态的解未知,需要用已经解决的状态推出。称为“从哪来”。

另一种转移思路是:当前状态的解已知,利用这个解,推出其他状态的解。称为“从哪去

1.6 两种转移方式

下面给出前面三个问题的两种转移方式的实现代码。

  • 例1.6.1
//台阶问题-从哪来

cin>>n;
f[1]=1; f[2]=2;
for (int i=3;i<=n;i++)
    f[i]=f[i-1]+f[i-2];
cout<<f[n]<<'\n';
  • 例1.6.2
//台阶问题-从哪去

cin>>n;
f[0]=1;  
for (int i=0;i<=n;i++)    //会超一点范围
{
    f[i+1]+=f[i];    //走一级或走两级
    f[i+2]+=f[i];
}
cout<<f[n]<<'\n';
  • 例1.6.3
// 硬币问题-从哪来

cin>>n;
memset(f,0x3f,sizeof(f));    //用了min,所以要赋大点的值
f[0]=0;
for (int i=1;i<=n;i++)
{
    f[i]=min(f[i],f[i-1]+1);
    if (i>=5) f[i]=min(f[i],f[i-5]+1);
    if (i>=11) f[i]=min(f[i],f[i-11]+1);
}
cout<<f[n]<<'\n';

注:0x3f一般可把可修改的左值设为较大的int值。

  • 例1.6.4
// 硬币问题-从哪去

cin>>n;
memset(f,0x3f,sizeof(f));    //用了min,所以要赋大点的值
f[0]=0;
for (int i=0;i<=n;i++)    //会超出一点范围
{
    f[i+1]=min(f[i+1],f[i]+1);
    f[i+5]=min(f[i+5],f[i]+1);
    f[i+11]=min(f[i+11],f[i]+1);
}
cout<<f[n]<<'\n';
  • 例1.6.5
//最长上升子序列-从哪来

cin>>n;
for (int i=1;i<=n;i++)
    cin>>a[i];
    
f[1]=1;
for (int i=2;i<=n;i++)
    for (int j=1;j<i;j++)
        if (a[j]<a[i]) f[i]=max(f[i],f[j]+1);

int maxn=0;
for (int i=1;i<=n;i++)
    maxn=max(maxn,f[i]);
cout<<maxn<<'\n';
  • 例1.6.6
//最长上升子序列-从哪去

cin>>n;
for (int i=1;i<=n;i++)
    cin>>a[i];
    
f[1]=1;
for (int i=1;i<n;i++)
    for (int j=i+1;j<=n;j++)
        if (a[i]<a[j]) f[j]=max(f[j],f[i]+1);

int maxn=0;
for (int i=1;i<=n;i++)
    maxn=max(maxn,f[i]);
cout<<maxn<<'\n';

1.7 动态规划总结

如果用动态规划来解决一个题目,你需要如下的“三连”:

  1. 设计状态:要选择出正确的状态。
  2. 得出转移方程:最难也是最重要的一步。
  3. 考虑如何实现(从哪来,从哪去)

决策类的动态规划,设计状态时,需要满足两个原则:

  1. 最优子结构:大问题的最优解,一定是由小问题的最优解推出来的。
  2. 无后效性:现在的决策,只与过去的结果有关,与过去的决策无关。

1.8 记忆化搜索

文章“递推与递归”的2.4 实例-求斐波那契数(一)*中提到过了记忆化。记忆化可以减少递归过程中的重复计算,大大降低时间复杂度。记忆化的基本操作如下:

  1. 如果该值未被计算,则计算出该值后存储该值并使用。
  2. 如果该值被计算过,直接使用存储的值。

一般而言,当计算出的值不会为0时,我们用元素的值是否为0来判断是否被计算,如果会为0的话,则需要新建一个vis数组来判断该值是否被计算过。

再贴一次代码。

  • 例1.8.1
int vis[1000005];    //如果求出的f[n]值为0时需要使用vis
int f[1000005];
long long Fibonacci(int n)
{
    if (n<=1) return 1;
    if (!f[n]) 
    	f[n]=Fibonacci(n-1)+Fibonacci(n-2)
    return f[n];
}

一个例题,try一下。


背包部分已转移。

感谢浏览😝!

此文章可能会在后续更新,欢迎纠错。