面试爬楼梯问题

2024-06-14 10:29:08 浏览数 (1)

今天我们来研究下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))

0 人点赞