爬楼梯问题

有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。

这个问题的解法有非常多的组合.来思考一下:
走上10级只有两种情况,从8级走上来的,和从9级走上来的.假设走到8级有x种走法,走到9级有y种走法,那么走到10级则有x+y种走法.
同样的道理走上9级也只有两种走法,分别是从7级走到9级,和从8级走到9级.

以此类推可以得出以下公式,某一级的走法是下两级走法的和:

$F(1) = 1$

$F(2) = 2$

$F(n) = F(n-1)+F(n-2) \quad (n \geq3)$

根据上述公式可以将 $F(10)$ 向下递归,这相当从后向前的枚举法.时间复杂度是指数级的.

把上面的枚举法画出来,发现有好多的重复计算:

有没有办法可以避免重复计算呢?最简单的想法是用缓存将计算结果存起来,再次计算的时候从缓存里面取结果,这就是备忘录算法.

其实还有个更好的解决方案,甚至连缓存都不需要,这就是动态规划算法,看下面的表格:

发现后一个状态只依赖于前两个状态,所以只需保留两个状态一次递推到10级即可.不知道聪明的你有没有看出来,动态规划本质上是穷举法，只是不重复计算罢了。

动态规划在导航中的应用

电子地图可以轻松为我们规划出两地之间的最短线路,这里也用到了动态规划算法.因为地图中的节点太多,如果遍历所有可能的路径找到两地的最短线路,复杂度是非常大的.

当找上海到北京的最短线路,不妨想这样一个问题,假设已经找到最短线路,这个线路经过南京,那么上海到南京的距离必然是最短的,南京到北京的距离也必然是最短的,于是上海到北京的最短线路可以分解为:

$min(上海-北京) = min(上海-南京) + min(南京-北京)$

当然,我们现在并不知道最短线路,也并不知道最短线路经过南京,但是没关系,只要在地图上横切一刀,把从上海到北京的任何线路一份为二:

那么从上海到北京的最短线路必然经过线上的某个点,我们可以先找到这条线上所有点的最短路径:

全程最短路线一定包含在这些局部最短路径中,于是我们将寻找全局最短路径的问题,分解为很多个寻找局部最短路径的问题.

上面的例子,每加入一条横切线,假设线上有10个城市,从上海到北京最多经过15个城市,那么采用动态规划的计算量是10x10x15,而采用枚举的计算量是 $10^{15}$ ,前后相差万亿倍.

维特比算法是一个特殊但应用最广的动态规划算法.利用动态规划可以解决任何一个图中的最短路径问题.而维特比算法是针对一个特殊的图-篱笆网络的有向图最短路径问题而提出的.它之所以重要,是因为凡是使用隐马尔科夫模型描述的问题都可以用它来解码,包括今天的数字通信,语音识别,机器翻译,拼音转汉字,分词等.

上图是一个篱笆网络,每个节点代表一个值,要求路径上所有值的乘积最大的路径.如果使用遍历的方式,那么路径的不同组合太多,复杂度会很高.

用动态规划的思想来思考:假设我们知道了最优路径,那么最优路径一定会经过第i层的节点,如果求出到第i层所有节点的最优路径,那么全局最优路径一定在这些局部最优路径中.

所以动态规划的求解过程:

参考:
<数学之美>
https://www.sohu.com/a/153858619_466939

posted @ 2019-01-11 15:03:00

评论加载中...