粗析动态规划DP

在吃了几次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