Unique Paths

Problem: Unique Paths

It's a simple dynamic programming. Solution for each node is decided by the sum of its right node and its down node.

Code in Python:

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[0] * n for _ in xrange(m)]

        for i in xrange(m):
            dp[i][-1] = 1
        for i in xrange(n):
            dp[-1][i] = 1

        for i in xrange(m-2, -1, -1):
            for j in xrange(n-2, -1, -1):
                dp[i][j] = dp[i+1][j] + dp[i][j+1]

        return dp[0][0]