Chương trình tìm số cách leo cầu thang (tối đa k bước 3) trong Python

Giả sử có một cầu thang n bậc và một số k. Ban đầu ở bậc 0, có thể leo 1, 2 hoặc 3 bậc mỗi lần, nhưng chỉ được leo 3 bậc tối đa k lần. Tìm số cách leo cầu thang.

Ví dụ, n = 5, k = 2, đầu ra là 13. Các cách leo:

• [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]

Các bước giải quyết:

• Nếu n == 0 hoặc n == 1, trả về 1.
• k = min(k, n).
• Tạo ma trận memo kích thước (n+1) x (k+1).
• Khởi tạo: với mọi r từ 0 đến k, gán memo[r][0]=1, memo[r][1]=1, memo[r][2]=2.
• Với i từ 3 đến n: memo[0][i] = memo[0][i-1] + memo[0][i-2].
• Với j từ 1 đến k:
  • Với i từ 3 đến n:
    • count = i // 3.
    • Nếu count <= j: memo[j][i] = memo[j][i-1] + memo[j][i-2] + memo[j][i-3].
    • Ngược lại: memo[j][i] = memo[j][i-1] + memo[j][i-2] + memo[j-1][i-3].
• Trả về memo[k][n].

Ví dụ minh họa

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))

Đầu vào

5, 2

Đầu ra

13