파이썬에서 계단을 오를 수 있는 방법(최대 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에 대해
- 메모[r, 0]:=1, 메모[r, 1]:=1, 메모[r, 2]:=2
3에서 n 사이의 i에 대해 다음을 수행합니다.
- 메모[0, i]:=메모[0, i-1] + 메모[0, i-2]
1~k 범위의 j에 대해 다음을 수행합니다.
- 3에서 n 사이의 i에 대해 다음을 수행합니다.
  - count :=i/3의 몫
  - 카운트 <=j이면
    - 메모[j, i]:=메모[j, i-1] + 메모[j, i-2] + 메모[j, i-3]
  - 그렇지 않으면
    - 메모[j, i]:=메모[j, i-1] + 메모[j, i-2] + 메모[j-1, i-3]
반품 메모[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