面试爬楼梯问题
原创
今天我们来研究下leetcode的一道 经典题目：
楼梯有n阶台阶，一次可以上1阶、2阶或者3阶台阶，使用递归的方法计算出有多少种走完楼梯的方式。
本题大家如果没有接触过的话，会感觉比较难，多举几个例子，就可以发现其规律。
爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。
那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。
所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。
所以为了解决这道问题，我们把它分割成很多小的子问题，当然也想到这其实是个递归问题。像第一次碰到这种动态规划的问题，往往都会手足无措很烧脑，这种只能练习、再练习、多练习来增加我们对这种问题的敏感性。
现在来试着从下到上解决这个动图规划问题，而不是从上到下。
伪代码就是：
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来实现就是
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))原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
腾讯云开发者
