บันได n ขั้น เดินได้ 1,2,3 ขั้นต่อครั้ง แต่เดิน 3 ขั้นได้สูงสุด k ครั้ง หาจำนวนวิธีเดินถึงขั้น n
ตัวอย่าง: n=5, k=2 → 13 วิธี
Dynamic Programming
memo[j][i]: วิธีเดิน i ขั้น โดยใช้ขั้น 3 ได้สูงสุด j ครั้ง- Base: memo[j][0]=1, [1]=1, [2]=2
- Transition: ถ้า i//3 ≤ 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]
การนำไปใช้
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] = 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(5, 2)) # 13
