পাইথনে n সংখ্যার ধাপের সংখ্যা গণনা করার প্রোগ্রাম

ধরুন আমাদের একটি সংখ্যা 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))