首页 > Python算法 > 动态规划 阅读数:34

爬楼梯问题—动态规划经典题目

我们再用动态规划来研究一个比较有代表性的问题——爬楼梯问题。

1. 问题描述

假设小明住在二楼,每次回家都需要经过一个有 10 层台阶的楼梯。小明每次可以选择一步走一级台阶或者一步走两级台阶。请计算一下小明从楼下到家一共有多少种走法?

打个比方,小明可以选择每次都只走一级台阶,那么小明回家一共需要走 10 步,这是其中的一种走法。或者,小明还可以选择每次都只走两级台阶,那么小明回家一共需要走 5 步,这是另外一种走法。除此之外,如果每次可以选择走一级或者两级,还会产生很多种不同的走法,现在我们要做的是把所有可能的走法数量统计出来。

2. 问题分析

1) 分析原问题最优解的结构特征

我们先从后往前分析问题的最优子结构。考虑小明走最后一步的情况,他要么是从第九级台阶再走一级到第十级,要么是从第八级台阶走两级到第十级,如图 1 所示。也就是说,要想到达第十级台阶,最后一步一定是从第八级或者第九级台阶开始的。为了描述方便,我们用 F(n) 表示第 n 级台阶的走法数量。
到达第十级台阶的前一步可选的方案
图 1:到达第十级台阶的前一步可选的方案

也就是说,如果已知从地面到第八级台阶 F(8) 一共有 X 种走法,从地面到第九级台阶 F(9) 一共有 Y 种走法,那么从地面走到第十级台阶 F(10) 一定是 X 和 Y 之和,即 F(10)=F(9)+F(8)。这是因为最后一步只有两种走法,所以倒数第二步只有两种情况。综合起来,这两种情况既没有重复也没有缺漏,故可以相加得到最后结果。

那么推而广之,我们可以通过对 F(n-1) 和 F(n-2) 进行计算得到 F(n)。F(n) 的最优解,包含了子问题 F(n-1) 和 F(n-2) 最优解,这是应用动态规划的一个重要基础。这里可以用反证法证明 F(n-1) 和 F(n-2) 如果不是最优子结构,将与本问题的最初假设不符。具体的表述我们留到讲解经典的“0-1 背包问题”时再呈现。

2) 建立递归关系,写出状态转移函数

通过上面的分析,我们可以得出 F(n)=F(n-1)+F(n-2)。这里要注意初始条件的确定,即当只有一级和两级台阶时的情况,因为 F(0) 往前对于该问题是没有意义的。由于问题比较简单,我们可以直接分析得出结论,即该问题的初始条件为 F(1)=1、F(2)=2。这里我们列出第二级台阶的走法示例,如图 2 所示。
到达第二级台阶的可选方案
图 2:到达第二级台阶的可选方案

分析到这里,该问题作为动态规划问题求解的要素就全部出现了。
  • 初始条件:F(1)=1,F(2)=2。
  • 最优子结构:F(n) 的最优子结构即 F(n-1) 和 F(n-2)。
  • 状态转移函数:F(n)=F(n-1)+F(n-2)。

至此,爬楼梯问题的动态规划建模过程已经完成。

3) 计算最优解的值

考虑算法的时间和空间效率问题,为了避免重复计算重叠子问题的解,我们利用最优子结构特性,采用自底向上的方式进行计算,具体过程如下。

根据边界定义,我们已经知道前两级台阶的走法数量,如表 1 所示。

表 1:前两级台阶的走法数量对照表
台阶数 1 2 3 4 5 6 7 8 9 10
走法数 1 2                

表 1 中第一行表示楼梯的台阶数量,第二行中对应的各列表示针对各级台阶可能的走法数量。在后续的求解过程中,我们可以利用表格中已知的子问题的解,根据状态转移函数,获得新的阶段的子问题的解,通过迭代,不断将表格填满,从而得到该问题的最终解。

在第一次迭代过程中,台阶数量为 3,根据状态转移函数,可知 F(3)=F(2)+F(1)=3,因此目前求解状态如表 2 所示。

表 2:第三级台阶的走法数量对照表
台阶数 1 2 3 4 5 6 7 8 9 10
走法数 1 2 3              

在第二次迭代过程中,台阶数量为 4,根据状态转移函数,可知 F(4)=F(3)+F(2)=5,因此目前求解状态如表 3 所示。

表 3:第四级台阶的走法数量对照表
台阶数 1 2 3 4 5 6 7 8 9 10
走法数 1 2 3 5            

以此类推,经过 8 次迭代之后,即可获得第十级台阶的走法数量,如表 4 所示。

表 4:各级台阶的走法数量对照表
台阶数 1 2 3 4 5 6 7 8 9 10
走法数 1 2 3 5 8 13 21 34 55 89

总结上面的过程,对每一级楼梯的走法数量而言,其求解过程所依赖的,都是其前一级和前两级楼梯的走法数量。因此,在每一次迭代过程中,仅需要关注这两个变量的取值,即可获得所求的新的变量的值。

4) 构造最优解

由于这个问题比较简单,只是列出数量,我们无须悉心构造,已经得出答案。

上面这个问题的形式,看起来是不是有点眼熟?是不是和我们很熟悉的斐波那契数列十分接近?但是在求解这个问题的过程中我们没有用以前递归的方法,而是使用了动态规划的思路,从底向上进行计算,避免了递归中大量的重复计算。例如,计算 F(10) 需要先计算 F(8),计算F(9)同样需要先计算F(8),底层的在递归中也都至少重复计算了一次。动态规划对每个子问题却只计算了一次。

3.  参考实现

下面,我们来把这个过程转化为程序。

我们定义函数 goUpStairs(n) 来计算第 n 级台阶的走法数量。在正式迭代之前,首先界定初始条件和边界的情况。当 n 小于 1 时,该输入变量不合法,返回的走法数量为 0;当 n 为 1 时,即为第一种初始边界条件的情况,返回值为 1;当 n 为 2 时,即为第二种初始边界条件的情况,返回值为 2。

之后即进入循环的迭代过程,在迭代中,根据之前的分析,我们仅需要关注 n-1 和 n-2 的取值,即可通过状态转移函数 F(n)=F(n-1)+F(n-2) 获得 F(n) 的值,因此,整个迭代过程仅需要引入一个临时变量循环保存当前子问题的解即可。

由此可见,该解决方案的时间复杂度为 O(n),而空间复杂度只有 O(1)。

具体实现如下,我们首先定义边界值,确定 F(1) 和 F(2) 的取值。之后,通过函数 goUpStairs(n) 迭代计算到达各层楼梯的走法数量并输出,最终获得问题的解。

爬楼梯问题代码如下:
def goUpStairs(n):
    if n < 1:         #判断当前台阶级数小于1
        return(0)
    if n == 1:        #判断当前台阶级数为1
        return(1)
    if n == 2:        #判断当前台阶级数为2
        return(2)
    a = 1   #初始化边界值
    b = 2
    sum = 0
    for i in range(2,n):    #迭代求解各级台阶的走法数量
        sum = a + b
        a = b
        b = sum
    return(sum)        #输出计算结果
print(goUpStairs(10))
输出:

89