用Python编写的查找爬楼梯的方法（最多k次，最多步数）

假设我们有一个n个阶梯的楼梯，还有另一个数字k，最初我们在楼梯0，可以一次往上爬1、2或3个台阶，但我们最多只能连续爬3个台阶k次。现在我们必须找出我们可以爬上楼梯的方法数。

因此，如果输入是n = 5，k = 2，则输出将为13，因为有不同的方法可以爬楼梯 −

[1, 1, 1, 1, 1]
[2, 1, 1, 1]
[1, 2, 1, 1]
[1, 1, 2, 1]
[1, 1, 1, 2]
[1, 2, 2]
[2, 1, 2]
[2, 2, 1]
[1, 1, 3]
[1, 3, 1]
[3, 1, 1]
[2, 3]
[3, 2]

为了解决这个问题，我们将遵循以下步骤 −

如果n与0相同，则
- 返回1
如果n与1相同，则
- 返回1
k:= k和n中的最小值
memo:=大小为(n+1) ×(k+1)的矩阵
对于r在0到k的范围内进行，如下所示
- memo[r, 0]:= 1, memo[r, 1]:= 1, memo[r, 2]:= 2
对于i在3到n的范围进行，如下所示
- memo[0, i]:= memo[0, i-1] + memo[0, i-2]
对于j在1到k的范围进行，如下所示
- 对于i在3到n的范围进行，如下所示
  - count := i/3的商
  - 如果count≤j，则
  - memo[j, i]:= memo[j, i-1] + memo[j, i-2] + memo[j, i-3]
  - 否则，
  - memo[j, i]:= memo[j, i-1] + memo[j, i-2] + memo[j-1, i-3]
返回memo[k, n]

请看以下实现以更好地理解−

更多Python相关文章，请阅读：Python 教程

例子

class Solution:
   def solve(self, n, k):
      if n==0:
         return 1
      if n==1:
         return 1
      k= min(k,n)
      memo=[[0]*(n+1) for _in range(k+1)]
         for r in range(k+1):
            memo[r][0]=1
            memo[r][1]=1
            memo[r][2]=2
            for i in range(3,n+1):
               memo[0][i]=memo[0][i-1]+memo[0][i-2]
               for j in range(1,k+1):
                  for i in range(3,n+1):
                     count = i//3
                     if count<=j:
                        memo[j][i]=memo[j][i-1]+memo[j][i-2]+memo[j][i-3]
                     else:
                        memo[j][i]=memo[j][i-1]+memo[j][i-2]+memo[j-1][i-3]
         return memo[k][n]
ob = Solution()
print(ob.solve(n = 5, k = 2))