Python में k-नॉन-ओवरलैपिंग लाइन सेगमेंट के सेट की संख्या खोजने का प्रोग्राम

मान लीजिए एक रेखा पर n पॉइंट्स हैं, जहां iवां पॉइंट (0 से n-1 तक) पोजीशन x = i पर है, हमें ठीक k अलग नॉन-ओवरलैपिंग लाइन सेगमेंट खींचने के तरीकों की संख्या ढूंढनी है जैसे कि प्रत्येक सेगमेंट दो या अधिक पॉइंट्स को कवर करे। प्रत्येक लाइन सेगमेंट के एंडपॉइंट्स के इंटीग्रल कोऑर्डिनेट्स होने चाहिए। k लाइन सेगमेंट को दिए गए सभी n पॉइंट्स को कवर करने की जरूरत नहीं है, और वे एंडपॉइंट्स साझा कर सकते हैं। यदि उत्तर बहुत बड़ा है, तो परिणाम mod 10^9+7 वापस करें।

उदाहरण के लिए, यदि इनपुट है n = 4, k = 2, तो आउटपुट 5 होगा क्योंकि हम पांच संभावनाएं बना सकते हैं: [(0 to 2),(2 to 3)], [(0 to 1),(1 to 3)], [(0 to 1),(2 to 3)], [(1 to 2),(2 to 3)] और [(0 to 1),(1 to 2)]।

समाधान के चरण

1. m := 10**9 + 7
2. n := n - 1
3. dp() फंक्शन परिभाषित करें जो i, covered, j लेता है:
   • यदि i == n:
     • True वापस करें यदि j == k अन्यथा False
   • यदि j > k:
     • 0 वापस करें
   • ans := dp(i+1, False, j) + dp(i+1, True, j+1)
   • यदि covered True है:
     • ans := ans + dp(i+1, True, j)
   • ans % m वापस करें
4. मुख्य मेथड से dp(0, False, 0) वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

def solve(n, k):
    m = 10 ** 9 + 7
    n -= 1
    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