Pythonで階段を上る方法（最大k回までの最大ステップ数）を見つけるためのプログラム

n段の階段があり、別の番号kもあるとします。最初は階段0にあり、一度に1、2、または3段の階段を上ることができます。しかし、私たちはせいぜいk回しか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については、
  • memo [0、i]：=memo [0、i-1] + memo [0、i-2]
• 1からkの範囲のjについては、
  • 3からnの範囲のiについては、
    • 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]
• return memo [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