โปรแกรมนับจำนวนชุดของเส้นตรง k เส้นที่ไม่ทับซ้อนใน Python

ปัญหา

มีจุด n จุดบนเส้นตรง (ตำแหน่ง 0..n-1) หาจำนวนวิธีวาดเส้นตรง k เส้น ไม่ทับซ้อน แต่ละเส้นครอบคลุม 2 จุดขึ้นไป จุดปลายเป็นจำนวนเต็ม สามารถใช้ปลายร่วมกันได้ ผลลัพธ์ modulo 1e9+7

ตัวอย่าง

n=4, k=2 → 5 ([(0,2),(2,3)], [(0,1),(1,3)], [(0,1),(2,3)], [(1,2),(2,3)], [(0,1),(1,2)])

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

1. m := 10^9+7, n := n-1
2. DP: dp(i, covered, j) = วิธีจากจุด i, covered = จุด i-1 ถูกครอบคลุมอยู่, j = จำนวนเส้นที่วาดแล้ว
   • ถ้า i == n: คืน j == k
   • ถ้า j > k: คืน 0
   • ans := dp(i+1, False, j) + dp(i+1, True, j+1) (เริ่มเส้นใหม่หรือไม่)
   • ถ้า covered: ans += dp(i+1, True, j) (ต่อเส้นเดิม)
   • คืน ans % m
3. คืน dp(0, False, 0)

การนำไปใช้งาน (Python)

def solve(n, k):
    m = 10 ** 9 + 7
    n -= 1
    from functools import lru_cache
    @lru_cache(None)
    def dp(i, covered, j):
        if i == n:
            return j == k
        if j > k:
            return 0
        ans = dp(i + 1, False, j) + dp(i + 1, True, j + 1)
        if covered:
            ans += dp(i + 1, True, j)
        return ans % m
    return dp(0, False, 0)

n = 4
k = 2
print(solve(n, k))

อินพุต

4, 2

เอาต์พุต

5