leetcode | 70.爬楼梯

70.爬楼梯

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
题目链接

思路

f(n) = f(n-1) + f(n-2)

1. 递归法
   由f(1)=1,f(2)=2,f(3)=3,…,以此类推,f(n)=f(n-1)+f(n-2),使用递归法实现该问题，递归方程为f(n)=f(n-1)+f(n-2),
   递归出口为f(1)=1,f(2)=2。

2. 记忆化递归法
   使用数组记录了每次计算的结果，避免递归法中的重复计算。

3. 动态规划
   动态规划转移方程：f(n)=f(n-1)+f(n-2)
   边界条件：f(1)=1,f(2)=2

4. 滚动数组
   使用长度为3的数组实现爬楼梯问题，问题中涉及三个状态:状态1、状态2、状态3，每次更新状态时，先将状态2移动到状态1
   的位置，再把状态3移动到状态2的位置，即将状态数组整体向前滚动一位。
   例：
   |1|2|3|—>|2|3|5|

   代码

   class Solution(object):

    def climbStairs(self, n):
        """
        递归法
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        if n == 2:
            return 2
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)
    
    def climbStairs2(self, n):
        """
        记忆化递归法
        :type n: int
        :rtype: int
        """
        memo = []
        return self.climbStairsMemo(n, memo)
    
    def climbStairsMemo(self, n, memo):
        if memo[n] > 0:
            return memo[n]
        if n == 1:
            memo[n] = 1
        elif n == 2:
            memo[n] = 2
        else:
            memo[n] = self.climbStairsMemo(n - 1, memo) + self.climbStairsMemo(n - 2, memo)
        return memo[n]
    
    def climbStairs3(self, n):
        """
        动态规划
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        dp = [1, 2]
        for i in range(2, n):
            dp.append(dp[i-1]+dp[i-2])  # dp[i] = dp[i-1] + dp[i-2]
        return dp[n-1]
    
    def climbStairs4(self, n):
        """
        滚动数组（斐波那契数列）
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        first = 1
        second = 2
        for i in range(2, n):
            third = first + second
            first = second
            second = third
        return second
        
   

   if name == “main“:

    slt = Solution()
    # numberOfSolutions = slt.climbStairs(2)
    # numberOfSolutions = slt.climbStairs2(2)
    # numberOfSolutions = slt.climbStairs3(2)
    numberOfSolutions = slt.climbStairs4(4)
    print(numberOfSolutions)