MENU

粗析动态规划DP

April 4, 2020 • Read: 592 • 算法

在吃了几次DP的亏以后,我终于开始着手准备DP的博文了……

首先推荐一篇图文:

https://mp.weixin.qq.com/s/3h9iqU4rdH3EIy5m6AzXsg

转自程序员小灰,侵删

图文所使用的JAVA代码我已经将其转换为了CPP代码并贴于文末,有兴趣自取~~

首先让我们来了解一下,什么是动态规划

动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划 ——引用自百度百科

动态规划题目的特点:

1.计数
  • 有多少种方式走到右下角
  • 有多少种方法挑选出K个数使得和为sum
  • ……
2.求最大最小值
  • 从左上角走到右下角路径的最大数字和
  • 最长上升子序列长度
  • ……
3.求存在性
  • 取石子游戏,先手是否获胜
  • 能不能选出K个数使得和为sum
  • ……

但是如果要求输出所有的情况,则不是动态规划的题目,此时应当考虑深搜或者迭代

动态规划的题目没有固定的模板(变化比较多),一般难度比较高,属于中上难度,是必须要掌握的算法

动态规划有三个重要的概念:

  1. 最优子结构:问题的最优解由相关子问题的最优解集合组成
  2. 边界:问题的边界,得到有限的结果
  3. 状态转移公式:问题每一阶段和下一阶段的关系

动态规划解题步骤:

说明:这里我们直接借用侯老师的视频给大家解释,因为视频时间较长,我给大家总结了关键点

https://www.bilibili.com/video/av45990457/

首先引入一个题目:

我有十级台阶,每次可以上一级或者两级,我上完整个台阶有多少钟方法?

看完这个题目,你或许想的是用排列组合的思想,写一个多层的虚幻遍历所有的情况然后统计最后的答案吧,但是这种算法所需的时间复杂度确实太大O(n2),那有没有更优秀的算法呢?

当然有!

有请今天的主角——动态规划

要写出动态规划的题,我们需要如下3个步骤

1.确定状态

确定状态需要两个意识:

  • 最后一步
  • 子问题

我们首先来确定最后一步

在刚刚列出的问题中,最后一步有两种走法:

走一步和走两步,这两种走法都是固定的

然后我们再来看看,假设走到第九级有X种走法,走到第八级有Y种走法

那么,走到第十级有多少种走法呢?

哈哈,当然是X+Y种啦!因为走到第九级的时候,就只有一种走法——走一步了

走到第八级的时候,也只能走两步,因为如果走一步的话,就包含在走到九级的情况中了

所以走到十级的情况只有X+Y

2.转移方程

现在,我们把走到第十级的方法数表示为F(10)

走到第九级和第八级的方法数分别表示为F(9),F(8)

所以有F(10)=F(9)+F(8)

同理,有F(9)=F(8)+F(7),F(8)=F(7)+F(6)……

于是我们归纳出如下一个公式:

F(n)=F(n-1)+F(n-2)

这就是这道题阶段与阶段间的状态转移方程,决定了问题的每一个阶段和下一个阶段的关系

3.初始条件和边界情况

但是当我们计算到最后一级或者两级台阶的时候,我们便无需继续计算,于是F(1)和F(2)便是问题的边界,但是如果一个问题没有边界,那么我们永远无法得到一个有限的结果

解决了如上三个问题,接下来便是写代码了

或许你会说,噫,不就是个递归么,好办!但是如果仔细分析,你会发现,如果使用递归,时间复杂度依旧是O(n2),这就不是我们费劲来寻找更快的算法的理由的,在这个递归中,出现了大量的重复计算,比如F(10)=F(9)+F(8),F(9)=F(8)+F(7),F(8)=F(7)+F(6),里面的F(8)便被计算了两次,当F(n)中n的值足够大时,里面重复计算的就更多,也许聪明的你很快就想到了使用备忘录算法来解决这件事,但是使用备忘录算法的空间复杂度却有O(n),这也是一个比较让人头疼的事情

那么……有没有更好的解决办法呢?

突然,一个小伙伴发现,这个……莫非解释传说中的肥波纳妾数列?(斐波那契数列)

是的,按照斐波那契数列的计算方式,我们可以很快的列出式子来解决这个问题

int get_climbing_way(int n){
    if (n<1) return 0;
    if (n==1) return 1;
    if (n==2) return 2;
    int a=1,b=2,tmp=0;
    for (int i=3;i<=n;i++){
        tmp=a+b;
        a=b;
        b=tmp;
    }
    return tmp;
}

程序从i=3开始迭代,一直到i=n结束,时间复杂度O(n),空间复杂度O(1),是不是很便捷的算法呢?

当然,本文只是粗略的解析了一下动态规划,因为DP的变数实在太多,还是应当多加练题才能彻底参透DP

例题:

洛谷P1192

洛谷P1103

番外个体

1.图文代码翻译:备忘录算法

int get_climbing_ways(int n){
    if (n<1) return 0;
    if (n==1) return 1;
    if (n==2) return 2;
    if (s.count(n)) return s[n];
    int value=get_climbing_ways(n-1)+get_climbing_ways(n-2);
    s[n]=value;
    return value;
}

2.最后给个答案吧:89

Last Modified: April 11, 2021
Archives Tip
QR Code for this page
Tipping QR Code