Leetcode 62. Unique Paths

https://leetcode.com/problems/unique-paths/

Interesting problem, where dynamic programming (DP for short) is just the right solution, because the result before affects the result after.

Performing DP needs two things: get the right start values and correct formula.

For this problem, we perform DP on this m x n board (sometimes you need to expand it to m+1 x n+1), the value of edges on top and left is 1 because only 1 way to go there. The formula is easy: dp[i][j] = dp[i-1][j] + dp[i][j-1], namely one spot's routine number equals its top and left routines.

Solution:

# T:O(m*n) S:O(m*n)
class Solution:
    # @param {integer} m
    # @param {integer} n
    # @return {integer}
    def uniquePaths(self, m, n):
        if m == 1 or n == 1:
            return 1
        dp = [([0]*n) for i in xrange(m)]
        for i in xrange(n):
            dp[0][i] = 1
        for i in xrange(m):
            dp[i][0] = 1
        for i in xrange(1, m):
            for j in xrange(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

Run Time: 64 ms