爬楼梯问题

来自计算思维百科
跳转至: 导航搜索
爬楼梯问题.png

一个人上台阶可以一次上1个或者2个,问这个人上n阶的台阶,总共有几种走法?

如有四层台阶,共有5种走法:

1+1+1+1=4;

1+2+1=4;

2+1+1=4;

1+1+2=4;

2+2=4;

涉及的计算思维

解决这个问题可以有三种方法,第一种是穷举法,适用于台阶总数较少时,穷举法体现了计算思维的机械化思想;第二种是递归法,找出公式进行递归,体现了计算思维的问题约简思想;第三种是动态规划法,把大问题分解成小问题,体现了计算思维的优化思想。

解决方案

方案一——穷举法

该方法的思想就是把所有上楼梯的组合一一列举出来,每次只上1个的、每次只上2个的、1个和两个交叉上的,挑选正好上了n层楼梯的组合作为问题的解。此方法只适用于总台阶数较少的情况。

方案二——递归法

我们可以把爬楼梯从反向角度看,即下楼梯,我们记f(n)表示下n层楼梯的方法总数,因为有两种方式可走,那么有f(n)=f(n-1)+f(n-2)这个递推公式,其中f(n-1)表示第一次下1步后的数目,f(n-2) 表示第一次下2步后的数目。其中,问题的初始值可以比较简单地得到f(1) = 1(一层楼梯只有一种走法), f(2) = 2(二层楼梯有2中走法)。利用递归思想,就可以推算出n层楼梯的走法。

方案三——动态规划法

在上面的方法中,存在重复计算的问题,例如在计算f(8)时,会多次重复计算f(5)这个子问题。为了提高效率,需要把这些子问题的解都记录下来,以空间换取时间。这种方法称为动态规划法