动态规划算法的理解

type

status

date

slug

summary

什么是动态规划？

动态规划（Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

💡

“dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.”

简单来说，动态规划其实就是，给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后，把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解。一般这些子问题很相似，可以通过函数关系式递推出来。动态规划就致力于解决每个子问题一次，减少重复计算，比如斐波那契数列就可以看做入门级的经典动态规划问题。

动态规划核心思想

动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。

下面是一个典型的例子：

A ： "1+1+1+1+1+1+1+1 =？"

A ： "上面等式的值是多少"

B ：计算 "8"

A : 在上面等式的左边写上 "1+" 呢？

A : "此时等式的值为多少"

B : 很快得出答案 "9"

A : "你怎么这么快就知道答案了"

A : "只要在8的基础上加1就行了"

A : "所以你不用重新计算，因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间"

一个例子走进动态规划 -- 青蛙跳阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。

解题思路：

要想跳到第10级台阶，要么是先跳到第9级，然后再跳1级台阶上去;要么是先跳到第8级，然后一次迈2级台阶上去。

同理，要想跳到第9级台阶，要么是先跳到第8级，然后再跳1级台阶上去;要么是先跳到第7级，然后一次迈2级台阶上去。

要想跳到第8级台阶，要么是先跳到第7级，然后再跳1级台阶上去;要么是先跳到第6级，然后一次迈2级台阶上去。

……总结即为：

当只有2级台阶时，有两种跳法，第一种是直接跳两级，第二种是先跳一级，然后再跳一级。即f(2) = 2;

当只有1级台阶时，只有一种跳法，即f（1）= 1；

暴力递归

用递归去解决这个问题：

但是，发现，真的很慢>_<

原因在于采用递归算法时存在大量重复计算，比如f（8）被计算了两次，f（7）被重复计算了3次...所以这就是递归算法低效的原因，即存在大量的重复计算！

那能否对递归进行一点修改呢？

带备忘录的递归解法（自顶向下）

一般使用一个数组或者一个哈希map充当这个备忘录。

第一步，f（10）= f(9) + f(8)，f(9) 和f（8）都需要计算出来，然后再加到备忘录中；

第二步， f(9) = f（8）+ f（7），f（8）= f（7）+ f(6), 因为 f(8) 已经在备忘录中啦，所以可以省掉，f(7),f（6）都需要计算出来，加到备忘录中；

第三步， f(8) = f（7）+ f(6),发现f(8)，f(7),f（6）全部都在备忘录上了，所以都可以剪掉；

……

带备忘录的递归算法，子问题个数=树节点数=n，解决一个子问题时间为一个加法的消耗，即为O(1),所以带备忘录的递归算法的时间复杂度是O(n)，空间复杂度为O(n)。示例代码如下：

自底向上的动态规划

动态规划跟带备忘录的递归解法基本思想是一致的，都是减少重复计算，时间复杂度也都是差不多。动态规划跟带备忘录的递归解法基本思想是一致的，都是减少重复计算，时间复杂度也都是差不多。不过两者的思路有所区别：

带备忘录的递归，是从f(10)往f(1）方向延伸求解的，所以也称为自顶向下的解法。

动态规划从较小问题的解，由交叠性质，逐步决策出较大问题的解，它是从f(1)往f(10）方向，往上推求解，所以称为自底向上的解法。

动态规划有几个典型特征，最优子结构、状态转移方程、边界、重叠子问题。在青蛙跳阶问题中：

f(n-1)和f(n-2) 称为 f(n) 的最优子结构

f(n)= f（n-1）+f（n-2）就称为状态转移方程

f(1) = 1, f(2) = 2 就是边界

比如f(10)= f(9)+f(8),f(9) = f(8) + f(7) ,f(8)就是重叠子问题。

带备忘录的递归解法，空间复杂度是O(n)，而递归算法的f（n）只依赖前面两个数，所以只需要两个变量a和b来存储，就可以满足需求，因此空间复杂度是O(1)。

动态规划的一般解题思路

如果一个问题，可以把所有可能的答案穷举出来，并且穷举出来后，发现存在重叠子问题，就可以考虑使用动态规划。

比如一些求最值的场景，如最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等，都是动态规划的经典应用场景。

动态规划的解题思路

动态规划的核心思想就是拆分子问题，记住过往，减少重复计算。 并且动态规划一般都是自底向上的，基于青蛙跳阶问题，动态规划的思路：

穷举分析

确定边界

找出规律，确定最优子结构

写出状态转移方程

1. 穷举分析

当台阶数是1的时候，有一种跳法，f（1） =1

当只有2级台阶时，有两种跳法，第一种是直接跳两级，第二种是先跳一级，然后再跳一级。即f(2) = 2;

当台阶是3级时，想跳到第3级台阶，要么是先跳到第2级，然后再跳1级台阶上去，要么是先跳到第 1级，然后一次迈 2 级台阶上去。所以f(3) = f(2) + f(1) =3……

2. 确定边界

通过穷举分析，发现当台阶数是1的时候或者2的时候，可以明确知道青蛙跳法。f（1） =1，f(2) = 2，当台阶n>=3时，已经呈现出规律f(3) = f(2) + f(1) =3，因此f（1） =1，f(2) = 2就是青蛙跳阶的边界。

3. 找规律，确定最优子结构

一道动态规划问题，其实就是一个递推问题。假设当前决策结果是f(n),则最优子结构就是要让 f(n-k) 最优,最优子结构性质就是能让转移到n的状态是最优的,并且与后面的决策没有关系,即让后面的决策安心地使用前面的局部最优解的一种性质

n>=3时，已经呈现出规律 f(n) = f(n-1) + f(n-2) ，因此，f(n-1)和f(n-2) 称为 f(n) 的最优子结构。

4. 写出状态转移方程

穷举分析，确定边界，最优子结构，就可以得出状态转移方程：

leetcode案例分析

来看一道经典的leetcode题目：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

示例 2：

提示：

1 <= n <= 45

这个题目和本质就是青蛙跳楼梯，来看看有哪些解法

方法一：动态规划

用f(x) 表示爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：

f(x)=f(x−1)+f(x−2)

用「滚动数组思想」把空间复杂度优化成 O(1)。下面的代码中给出的就是这种实现。

复杂度分析

时间复杂度：循环执行 n 次，每次花费常数的时间代价，故渐进时间复杂度为 O(n)。 空间复杂度：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为 O(1)。

方法二：矩阵快速幂

这是官方给的一个方法，只能单押一个6。

上面的滚动数组的方法适用于 n 比较小的情况，在 n 变大之后，O(n)的时间复杂度会让这个算法看起来有些捉襟见肘。我们可以用「矩阵快速幂」的方法来优化这个过程。

首先我们可以构建这样一个递推关系：

因此我们只要能快速计算矩阵 M 的 n次幂，就可以得到 f(n) 的值。如果直接求取 M^n，时间复杂度是 O(n)的，我们可以定义矩阵乘法，然后用快速幂算法来加速这里 M^n的求取。

复杂度分析

时间复杂度：同快速幂，O(log⁡n)。

空间复杂度：O(1)。

方法三：通项公式

根据递推方程 f(n)=f(n−1)+f(n−2)，我们可以写出这样的特征方程：

复杂度分析

代码中使用的 pow函数的时空复杂度与 CPU 支持的指令集相关。

方式四：狼人大哥法

在提交的区域里看到一个狼人大哥(比狠人还多一点>-<),注意到题目中 • 1 <= n <= 45

所以他就直接穷举了

参考文献

https://zhuanlan.zhihu.com/p/365698607

https://leetcode.cn/problems/climbing-stairs/solutions/286022/pa-lou-ti-by-leetcode-solution/