পাইথনে K-নন-ওভারল্যাপিং লাইন সেগমেন্টের সেট সংখ্যা গণনার প্রোগ্রাম

মান লিজিয়ে একটি লাইনে n পয়েন্ট আছে, যেখানে i-তম পয়েন্ট (০ থেকে 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 হলে True অন্যথায় False রিটার্ন করুন।
- যদি j > k হয়, তবে 0 রিটার্ন করুন।
- ans := dp(i+1, False, j) + dp(i+1, True, j+1)
- যদি covered সত্য হয়, তবে ans += dp(i+1, True, j)
- ans % 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