Chương trình đếm số tập k đoạn thẳng không giao nhau trong Python

Có n điểm trên đường thẳng tại x=0..n-1. Vẽ đúng k đoạn thẳng không giao nhau (mỗi đoạn ≥ 2 điểm, đầu mút nguyên, có thể chia sẻ đầu mút). Đếm số cách, modulo 10⁹+7.

Ví dụ: n=4, k=2 → 5 cách: [(0,2),(2,3)], [(0,1),(1,3)], [(0,1),(2,3)], [(1,2),(2,3)], [(0,1),(1,2)].

Giải thuật (DP đệ quy + Memoization)

1. m = 10**9+7, n = n-1 (số khoảng giữa các điểm).
2. Hàm dp(i, covered, j): xét khoảng i, covered = khoảng trước có đang trong đoạn, j = số đoạn đã tạo.
   • Nếu i == n: trả về j == k.
   • Nếu j > k: trả về 0.
   • ans = dp(i+1, False, j) + dp(i+1, True, j+1) (không bắt đầu đoạn / bắt đầu đoạn mới).
   • Nếu covered: ans += dp(i+1, True, j) (tiếp tục đoạn hiện tại).
   • Trả về ans % m.
3. Gọi dp(0, False, 0).

Ví dụ minh họa

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

Đầu vào

4, 2

Đầu ra

5