假设我们有一个阶梯为n的楼梯，并且还有另一个数字k，最初我们位于楼梯0，可以一次爬1、2或3步。但我们最多只能攀3次楼梯。现在我们必须找到爬楼梯的方法。
因此，如果输入类似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的最小值
备忘：=大小为（n + 1）x（k + 1）的矩阵
对于0到k范围内的r，执行
memo [r，0]：= 1，memo [r，1]：= 1，memo [r，2]：= 2
对于3到n范围内的i
备忘录[0，i]：=备忘录[0，i-1] +备忘录[0，i-2]
对于1到k范围内的j，执行
count：= i / 3的商
如果count <= j，则
除此以外，
备忘录[j，i]：=备忘录[j，i-1] +备忘录[j，i-2] +备忘录[j，i-3]
备忘录[j，i]：=备忘录[j，i-1] +备忘录[j，i-2] +备忘录[j-1，i-3]
对于3到n范围内的i
返回备忘录[k，n]
让我们看下面的实现以更好地理解-
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))
5, 2
输出结果
13