ধরুন আমাদের একটি সংখ্যা n আছে আমাদের n সংখ্যার ধাপের সংখ্যা বের করতে হবে। আমরা জানি যে একটি সংখ্যাকে স্টেপিং নম্বর বলা হয় যখন সমস্ত সংলগ্ন সংখ্যার 1 এর পরম পার্থক্য থাকে। সুতরাং একটি সংখ্যা 123 হলে, এটি ধাপ সংখ্যা কিন্তু 124 নয়। যদি উত্তরটি খুব বড় হয় তবে ফলাফল মোড 10^9 + 7 ফেরত দিন।
সুতরাং, যদি ইনপুটটি n =2 এর মত হয়, তাহলে আউটপুট হবে 17, যেমন স্টেপিং নম্বরগুলি হল [12, 23, 34, 45, 56, 67, 78, 89, 98, 87, 76, 65, 54, 43, 32, 21, 10]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- m :=10^9 + 7
- যদি n 0 এর মত হয়, তাহলে
- রিটার্ন 0
- যদি n 1 এর মত হয়, তাহলে
- প্রত্যাবর্তন 10
- dp :=মান 1 দিয়ে ভরা 10 আকারের একটি তালিকা
- n - 1 বার পুনরাবৃত্তি করুন, করুন
- ndp :=মান 0 দিয়ে ভরা 10 আকারের একটি তালিকা
- ndp[0] :=dp[1]
- আমি 1 থেকে 8 রেঞ্জের জন্য, কর
- ndp[i] :=dp[i - 1] + dp[i + 1]
- ndp[9] :=dp[8]
- dp :=ndp
- রিটার্ন (dp এর সমস্ত সংখ্যার যোগফল [সূচী 1 থেকে শেষ পর্যন্ত]) mod m
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class Solution: def solve(self, n): m = (10 ** 9 + 7) if n == 0: return 0 if n == 1: return 10 dp = [1] * 10 for _ in range(n - 1): ndp = [0] * 10 ndp[0] = dp[1] for i in range(1, 9): ndp[i] = dp[i - 1] + dp[i + 1] ndp[9] = dp[8] dp = ndp return sum(dp[1:]) % m ob = Solution() n = 3 print(ob.solve(n))
ইনপুট
3
আউটপুট
32