পাইথনে অনন্য পথ

ধরুন একটি রোবট একটি n x m গ্রিডের (n সারি এবং m কলাম) উপরের-বাম কোণে অবস্থিত। রোবটটি যেকোনো সময় যে কোনো সময় নিচের দিকে বা ডান দিকে যেতে পারে। রোবট গ্রিডের নীচে-ডান কোণায় পৌঁছাতে চায় (নীচের চিত্রে 'END চিহ্নিত)। তাহলে আমাদের খুঁজে বের করতে হবে কতগুলো সম্ভাব্য অনন্য পথ? উদাহরণস্বরূপ যদি m =3 এবং n =2, তাহলে গ্রিডটি নীচের মত হবে −

আউটপুট হবে 3, তাই স্টার্ট পজিশন থেকে শেষ পজিশনে পৌঁছানোর মোট 3টি ভিন্ন উপায় রয়েছে। এই পথগুলি হল −

1. ডান → ডান → নিচে
2. ডান → নিচে → ডান
3. নিচে → ডান → ডান

আসুন ধাপগুলো দেখি -

• এটি সমাধান করতে আমরা ডায়নামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করব
• সারি দিন :=n এবং col :=m, n x m অর্ডারের একটি টেবিল ডিপি তৈরি করুন এবং এটি -1 দিয়ে পূরণ করুন
• DP[সারি – 2, col - 1] :=1
• আমি 0 থেকে col
  পরিসরে
  • DP[n – 1, i] :=1
• আমি 0 থেকে সারি
  এর মধ্যে
  • DP[i, col – 1] :=1
• আমি রেঞ্জ সারি -2 থেকে -1
  পর্যন্ত
  • j-এর জন্য রেঞ্জ col -2 থেকে -1
    পর্যন্ত
    • DP[i, j] :=DP[i + 1, j] + DP[i, j + 1]
• ডিপি ফেরত দিন[0, 0]

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

উদাহরণ

class Solution(object):
   def uniquePaths(self, m, n):
      row = n
      column = m
      dp = [[-1 for i in range(m)] for j in range(n)]
      dp[row-2][column-1] = 1
      for i in range(column):
         dp[n-1][i] = 1
      for i in range(row):
         dp[i][column-1]=1
      for i in range(row-2,-1,-1):
         for j in range(column-2,-1,-1):
            dp[i][j] = dp[i+1][j] + dp[i][j+1]
      return dp[0][0]
ob1 = Solution()
print(ob1.uniquePaths(10,3))

ইনপুট

10
3

আউটপুট

55