Python爬楼梯，一次只能上一阶或者两阶，一共有n阶，计算一共有多少种上法，用动态规则算法

Python爬楼梯，一次只能上一阶或者两阶，一共有n阶，计算一共有多少种上法，用动态规则算法，求问

n = 3
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        # base case
        if n == 0:
            return(0)
        if n == 1:
            return(1)
        if n == 2:
            return(2)
        
       
        methods_per_steps = [1,2]
        
        for i in range(2,n+1):
            methods_per_steps.append(methods_per_steps[i-1]+methods_per_steps[i-2])
        return(methods_per_steps[n-1])
        
out = Solution().climbStairs(n)
print(out)

def upstairs(num):
if num==1:
return 1
if num==2:
return 2

else:
    return upstairs(num-1)+upstairs(num-2)

num = input("请输入台阶级数:")
try:
num = int(num)
steps = upstairs(num)
print("一共有",steps,"种方法上台阶")
except Exception as e:
print("不是数字")

方法一（递归加缓存）

class Solution(object):
    def __init__(self):
        self.m = {}
 
    def add_end(self, arr, totalNum):
        tmpArr = []
        for innerItem in arr:
            sum_ = sum(innerItem)
            delta = totalNum - sum_
            if delta == 3 or delta == 1 or delta == 2:
                tmpArr.append(innerItem + [delta])
        return tmpArr
 
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: list
        """
        if n in self.m:
            return self.m[n]
        if n == 1:
            return [[1, ]]
        elif n == 2:
            return [[1, 1], [2, ]]
        elif n == 3:
            return [[1, 1, 1], [2, 1], [1, 2], [3, ]]
        else:
 
            f1 = self.add_end(self.climbStairs(n - 1), n)
            f2 = self.add_end(self.climbStairs(n - 2), n)
            f3 = self.add_end(self.climbStairs(n - 3), n)
            self.m[n] = f1 + f2 + f3
            return self.m[n]

方法二（线性）：

class Solution2(object):
 
    def add_end(self, arr, totalNum):
        tmpArr = []
        for innerItem in arr:
            sum_ = sum(innerItem)
            delta = totalNum - sum_
            if delta == 3 or delta == 1 or delta == 2:
                tmpArr.append(innerItem + [delta])
        return tmpArr
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: list
        """
        dp = [[] for _ in range(n)]
        dp[0] = [[1, ]]
        dp[1] = [[1, 1], [2, ]]
        dp[2] = [[1, 1, 1], [2, 1], [1, 2], [3, ]]
        if n == 1:
            return dp[0]
        elif n == 2:
            return dp[1]
        elif n == 3:
            return dp[2]
        for i in range(3, n):
            dp[i] = self.add_end(dp[i - 1], i+1) + self.add_end(dp[i - 2], i+1) + self.add_end(dp[i - 3], i+1)
        return dp[-1]