โปรแกรมนับวิธีตกลูกบอลไปชั้นล่างหลีกเลี่ยงขั้นแบนใน Python

คำอธิบายปัญหา

กำหนดความสูง h และ blacklist (ชั้นที่ตายทันที) เริ่มที่ชั้น h ต้องไปถึงชั้น 0 รอบคู่ (0,2,4...): เดินได้ 1,2,4 ขั้น รอบคี่: เดินได้ 1,3,4 ขั้น หาจำนวนวิธี modulo 10^9+7

ตัวอย่าง

h = 5, blacklist = [2, 1] → Output: 2

• รอบ 0: 5→4 (1 ขั้น), รอบ 1: 4→0 (4 ขั้น)
• รอบ 0: 5→3 (2 ขั้น), รอบ 1: 3→0 (3 ขั้น)

ขั้นตอนการแก้ปัญหา (DP)

1. dp[i][0] = วิธีไปถึงชั้น i จบที่รอบคู่, dp[i][1] = จบที่รอบคี่
2. dp[0] = [1, 1] (ฐาน)
3. สำหรับ i=1..h, ลองเดิน x=1,2,3,4:
   • x≠3: เพิ่มจาก dp[i-x][1] → dp[i][0] (รอบคู่เดิน 1,2,4)
   • x≠2: เพิ่มจาก dp[i-x][0] → dp[i][1] (รอบคี่เดิน 1,3,4)
4. ข้ามชั้นใน blacklist

การตนการทำงาน (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]
    m = 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] %= m
        dp[i][1] %= m
    return dp[h][0]

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

อินพุต / เอาต์พุต

Input:  5, [2, 1]
Output: 2