পাইথনে কে-নন-ওভারল্যাপিং লাইন সেগমেন্টের সেটের সংখ্যা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি রেখায় n বিন্দু আছে, যেখানে ith বিন্দু (0 থেকে n-1 পর্যন্ত) অবস্থান x =i-এ, আমাদেরকে ঠিক k ভিন্ন ভিন্ন অ-ওভারল্যাপিং রেখার অংশ আঁকতে পারার উপায় খুঁজে বের করতে হবে যাতে প্রতিটি সেগমেন্ট দুই বা ততোধিক পয়েন্ট কভার করে। প্রতিটি লাইন সেগমেন্টের শেষ বিন্দুতে অবিচ্ছেদ্য স্থানাঙ্ক থাকতে হবে। k রেখার অংশগুলিকে সমস্ত প্রদত্ত n পয়েন্টগুলি কভার করতে হবে না এবং তারা শেষ বিন্দুগুলি ভাগ করতে পারে৷ যদি উত্তরটি খুব বড় হয়, তাহলে ফলাফল মোড 10^9+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)]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

m :=10^9 + 7
n :=n - 1
একটি ফাংশন dp() সংজ্ঞায়িত করুন। এর জন্য i, covered, j
যদি i n এর মত হয়, তাহলে
- সত্য ফেরত দিন যদি j k এর মত হয় অন্যথায় মিথ্যা
যদি j> k হয়, তাহলে
উত্তর :=dp(i + 1, False, j) + dp(i + 1, True, j + 1)
যদি আচ্ছাদিত সত্য হয়, তাহলে
- উত্তর :=ans + dp(i + 1, True, j)
উত্তর mod m
প্রধান পদ্ধতি থেকে 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