পাইথনে n ডিস্টিংচ নোড দিয়ে সম্ভাব্য BST-এর সংখ্যা বের করা

একটি সংখ্যা n দেওয়া আছে। [1, 2, ..., n] মানগুলো দিয়ে কতটি ভিন্ন BST (বাইনারি সার্চ ট্রি) তৈরি করা যায় তা বের করতে হবে। উত্তর বড় হলে ১০⁹+৭ দিয়ে মডুলো করুন।

উদাহরণ

ইনপুট: n = 3

আউটপুট: 14

সমাধান পদ্ধতি

1. a := [0, 1]
2. m := 10⁹+7
3. max_n := 1000
4. k = 2 থেকে max_n + 1 পর্যন্ত:
   • a.append((1 + sum(a[i] * a[k - i] for i in range(1, k))) % m)
5. (a[n + 1] - 1) % m রিটার্ন করুন।

নোট: এটি ক্যাটালান সংখ্যা বা বেস্ট ক্যালকুলেশন의 একটি вариয়েশন।

পাইথন ইমপ্লিমেন্টেশন

def solve(n):
    a = [0, 1]
    m = 10**9 + 7
    max_n = 1000
    for k in range(2, max_n + 2):
        a.append((1 + sum(a[i] * a[k - i] for i in range(1, k))) % m)
    return (a[n + 1] - 1) % m

# টেস্ট
n = 3
print(solve(n))  # আউটপুট: 14

ইনপুট

3

আউটপুট

14