পাইথনে ব্ল্যাকলিস্টেড ধাপ এড়িয়ে বল নিচে আনতে পারার পথের সংখ্যা বের করার প্রোগ্রাম

ব্যাখ্যা:

• রাউন্ড ০: ১ ধাপ (৫→৪), রাউন্ড ১: ৪ ধাপ (৪→০)
• রাউন্ড ০: ২ ধাপ (৫→৩), রাউন্ড ১: ৩ ধাপ (৩→০)

সমাধানের পদ্ধতি (ডাইনামিক প্রোগ্রামিং)

1. blacklist কে সেটে রূপান্তর করুন
2. যদি ০ বা h ব্ল্যাকলিস্টে থাকে তবে ০ রিটার্ন করুন
3. dp অ্যারে তৈরি করুন আকার h+1, প্রতিটি উপাদান [0, 0]
4. dp[0] = [1, 1]
5. m = 10**9 + 7
6. i = 1 থেকে h পর্যন্ত:
   • x ∈ {1, 2, 3, 4} এর জন্য যদি i-x >= 0 এবং i-x ব্ল্যাকলিস্টে না থাকে:
     • যদি x != 3 হলে dp[i][0] += dp[i-x][1]
     • যদি x != 2 হলে dp[i][1] += dp[i-x][0]
   • dp[i][0] %= m, dp[i][1] %= m
7. dp[h][0] রিটার্ন করুন

পাইথন কোড

def solve(h, blacklist):
    blacklist = set(blacklist)
    if 0 in blacklist or h in blacklist:
        return 0
    dp = [[0, 0] for i in range(h + 1)]
    dp[0] = [1, 1]
    m = 10 ** 9 + 7
    for i in range(1, h + 1):
        for x in [1, 2, 3, 4]:
            if i - x >= 0 and i - x not in blacklist:
                if x != 3:
                    dp[i][0] += dp[i - x][1]
                if x != 2:
                    dp[i][1] += dp[i - x][0]
        dp[i][0] %= m
        dp[i][1] %= m
    return dp[h][0]

h = 5
blacklist = [2, 1]
print(solve(h, blacklist))  # আউটপুট: 2

টেস্ট কেস

ইনপুট: 5, [2, 1]
আউটপুট: 2