今天我们来研究下leetcode的一道 经典题目:
楼梯有n阶台阶,一次可以上1阶、2阶或者3阶台阶,使用递归的方法计算出有多少种走完楼梯的方式。
本题大家如果没有接触过的话,会感觉比较难,多举几个例子,就可以发现其规律。
爬到第一层楼梯有一种方法,爬到二层楼梯有两种方法。
那么第一层楼梯再跨两步就到第三层 ,第二层楼梯再跨一步就到第三层。
所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来,那么就可以想到动态规划了。
所以为了解决这道问题,我们把它分割成很多小的子问题,当然也想到这其实是个递归问题。像第一次碰到这种动态规划的问题,往往都会手足无措很烧脑,这种只能练习、再练习、多练习来增加我们对这种问题的敏感性。
现在来试着从下到上解决这个动图规划问题,而不是从上到下。
伪代码就是:
代码语言:txt复制f(i):
if i==N: return 1
if i>N: return 0
reutrn f(i 1) f(i 2) f(i 3)
在第0层,你有3个选择爬 stair ( i 1 ), stair ( i 2 ) 和 stair ( i 3 )。一旦爬上一次,你再次面临3个选择 stair ( i 1 ), stair ( i 2 ) 和 stair ( i 3 )。这就是问题的模式pattern。一旦到了第N层,return1代表 结束唯一选择。如果超过N,那么返回0,因为没有超过N层的阶梯,代表这次选择无效。
使用Python来实现就是
代码语言:python代码运行次数:2复制class Solution:
def _step(self, i: int, N: int) -> int:
if i==N:
return 1
if i>N:
return 0
return self._step(i 1, N) self._step(i 2, N) self._step(i 3, N)
def climbStairs(self, n: int) -> int:
if n <= 1:
return n
return self._step(0, n)
s=Solution()
print ("1 staris contain %d ways." % s.climbStairs(1))
print ("2 staris contain %d ways." % s.climbStairs(2))
print ("3 staris contain %d ways." % s.climbStairs(3))
print ("5 staris contain %d ways." % s.climbStairs(5))
print ("10 staris contain %d ways." % s.climbStairs(10))