পাইথনে ইউনিক পাথস (গ্রিডে রোবটের পাথ গণনা)

একটি n x m গ্রিডে রোবট টপ-লেফট থেকে বটম-রাইট যেতে চায়। শুধু ডাউন বা রাইট মুভ করতে পারে। কতটুকু ইউনিক পাথ আছে তা বের করতে হবে।

উদাহরণ: m=3, n=2 হলে আউটপুট ৩ (৩টি পাথ: R→R→D, R→D→R, D→R→R)।

সমাধান: DP টেবিল (n x m) -1 দিয়ে ফিল। DP[row-2][col-1]=1। লাস্ট রো ও লাস্ট কলাম ১ দিয়ে ফিল। বাকি সেলগুলো DP[i][j] = DP[i+1][j] + DP[i][j+1]।

উদাহরণ

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