Chương trình Python đếm số cách thả bóng xuống cấp độ 0 tránh bước đen

Cho chiều cao h và danh sách blacklist (các cấp độ cấm). Bắt đầu ở độ cao h, mục tiêu đưa bóng xuống độ cao 0. Luật di chuyển:

• Vòng chẵn (0, 2, 4...): di chuyển xuống 1, 2, hoặc 4 cấp.
• Vòng lẻ (1, 3, 5...): di chuyển xuống 1, 3, hoặc 4 cấp.

Ví dụ

Input: h = 5, blacklist = [2, 1]

Output: 2

Giải thích:

• Cách 1: Vòng 0: 5→4 (1 bước), Vòng 1: 4→0 (4 bước).
• Cách 2: Vòng 0: 5→3 (2 bước), Vòng 1: 3→0 (3 bước).

Thuật toán (Dynamic Programming)

1. Chuyển blacklist thành set tra cứu O(1). Nếu 0 hoặc h trong blacklist → trả về 0.
2. dp[i][0]: số cách đến độ cao i ở vòng chẵn.
   dp[i][1]: số cách đến độ cao i ở vòng lẻ.
3. Khởi tạo: dp[0] = [1, 1] (đã ở đích).
4. Duyệt i = 1..h:
   • Với mỗi bước x ∈ {1,2,3,4}:
     • Nếu i-x ≥ 0 và i-x không trong blacklist:
       • Nếu x != 3 → có thể đến từ vòng lẻ: dp[i][0] += dp[i-x][1]
       • Nếu x != 2 → có thể đến từ vòng chẵn: dp[i][1] += dp[i-x][0]
   • Mod 10⁹+7 sau mỗi cập nhật.
5. Kết quả: dp[h][0] (bắt đầu ở vòng 0 - chẵn).

Mã nguồn Python

def solve(h, blacklist):
    blacklist = set(blacklist)
    if 0 in blacklist or h in blacklist:
        return 0

    dp = [[0, 0] for _ in range(h + 1)]
    dp[0] = [1, 1]
    MOD = 10**9 + 7

    for i in range(1, h + 1):
        for x in [1, 2, 3, 4]:
            if i - x >= 0 and (i - x) not in blacklist:
                if x != 3:
                    dp[i][0] += dp[i - x][1]
                if x != 2:
                    dp[i][1] += dp[i - x][0]
        dp[i][0] %= MOD
        dp[i][1] %= MOD

    return dp[h][0]

# Test
h = 5
blacklist = [2, 1]
print(solve(h, blacklist))  # Output: 2

Độ phức tạp

• Thời gian: O(h) (4 bước cố định cho mỗi i).
• Không gian: O(h).