আমরা কে বার সরাতে পারি এবং পাইথনে প্রথম স্থানে ফিরে যেতে পারি তার সংখ্যা পরীক্ষা করার জন্য প্রোগ্রাম

ধরুন আমরা n দৈর্ঘ্যের তালিকার 0 অবস্থানে আছি, এবং প্রতিটি ধাপে, আমরা এক জায়গায় ডানে বা এক জায়গায় বামে যেতে পারি (সীমার বেশি নয়), বা একই অবস্থানে থাকতে পারি। এখন যদি আমরা ঠিক k পদক্ষেপ নিতে পারি, তাহলে আমাদের খুঁজে বের করতে হবে যে আমরা কতগুলি অনন্য হাঁটা নিতে পারি এবং সূচক 0 এ ফিরে যেতে পারি। উত্তরটি খুব বড় হলে এটি মোড 10^9 + 7 ফেরত দিন।

সুতরাং, যদি ইনপুটটি n =7 k =4 এর মত হয়, তাহলে আউটপুট হবে 9, কর্মগুলি যেমন-

[ডান, ডান, বাম, বাম],
[ডান, বাম, ডান, বাম],
[থাক, থাক, থাক, থাক],
[ডান, বাম, থাকুন, থাকুন],
[থাক, থাক, ডানে, বামে],
[ডান, থাকুন, থাকুন, বামে],
[ডান, থাকুন, বামে, থাকুন],
[থাক, ডানে, বামে, থাকো],
[থান, ডানে, থাকুন, বামে],

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

m :=10^9 + 7
N :=দৈর্ঘ্য
একটি ফাংশন dp() সংজ্ঞায়িত করুন। এটি i, জাম্প
যদি জাম্প 0 এর মত হয়, তাহলে
- রিটার্ন (সত্য যখন আমি 0 এর মত হয়, অন্যথায় মিথ্যা)
গণনা :=dp(i, জাম্প - 1)
যদি i>=0 হয়, তাহলে
- গণনা :=গণনা + dp(i + 1, জাম্প - 1)
যদি i <=N - 1, তারপর
- গণনা :=গণনা + dp(i - 1, জাম্প - 1)
রিটার্ন গণনা
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন:
রিটার্ন dp(0, n) mod m

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

class Solution:
   def solve(self, length, n):
      MOD = 10 ** 9 + 7
      N = length

      def dp(i, jumps):
         if jumps == 0:
            return +(i == 0)

         count = dp(i, jumps - 1)
         if i >= 0:
            count += dp(i + 1, jumps - 1)
         if i <= N - 1:
            count += dp(i - 1, jumps - 1)
         return count
      return dp(0, n) % MOD    
ob = Solution()
n = 7
k = 4
print(ob.solve(n, k))

ইনপুট

7, 4