पायथन में k-गैर-अतिव्यापी लाइन खंडों के सेट की संख्या खोजने का कार्यक्रम

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

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

म :=10^9 + 7
n :=n - 1
एक फ़ंक्शन को परिभाषित करें dp() । यह ले जाएगा मैं, कवर, जे
यदि मैं n के समान हूं, तो
- यदि j, k के समान है, अन्यथा असत्य है, तो सही लौटें
अगर j> k, तो
Ans :=dp(i + 1, False, j) + dp(i + 1, True, j + 1)
अगर कवर किया गया सच है, तो
- Ans :=ans + dp(i + 1, True, j)
वापसी उत्तर मोड एम
मुख्य विधि से वापसी 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