Chương trình đếm số cách đi k bước và quay về vị trí 0 bằng Python

Bắt đầu tại vị trí 0 của danh sách độ dài n. Mỗi bước có thể đi phải, trái (không vượt giới hạn) hoặc đứng yên. Tìm số đường đi duy nhất đúng k bước để quay về chỉ số 0. Kết quả lấy modulo 10^9+7.

Ví dụ: n = 7, k = 4 → 9 cách.

Giải thuật

• Sử dụng đệ quy có nhớ (memoization) hoặc quy hoạch động.
• Hàm dp(i, jumps): số cách từ vị trí i với jumps bước còn lại để về 0.
  • Cơ sở: jumps == 0 → trả về 1 nếu i == 0 ngược lại 0.
  • Đệ quy: dp(i, jumps-1) (đứng yên) + dp(i+1, jumps-1) (nếu i >= 0) + dp(i-1, jumps-1) (nếu i <= N-1).
• Trả về dp(0, k) % MOD.

Ví dụ minh họa

class Solution:
    def solve(self, length, n):
        MOD = 10**9 + 7
        N = length
        def dp(i, jumps):
            if jumps == 0:
                return int(i == 0)
            count = dp(i, jumps - 1)
            if i >= 0:
                count += dp(i + 1, jumps - 1)
            if i <= N - 1:
                count += dp(i - 1, jumps - 1)
            return count
        return dp(0, n) % MOD

ob = Solution()
n = 7
k = 4
print(ob.solve(n, k))

Đầu vào

7, 4

Đầu ra

9