Unique Paths

Medium, Dynamic Programming

Question

一个机器人在mxn的矩阵的左上角，想要移动到右下角，它只能向右或者向下移动，请问有多少不同路径

上图是 3 x 7 的矩阵.

Note: m and n will be at most 100.

Answer

典型的DP问题。（r,c)格点有两个选择, (r, c) --> (r+1, c)或者(r, c) --> (r, c+1)，UP(r, c) == UP(r+1, c) + UP(r, c+1).

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        mat = [[-1 for j in range(n+1)] for i in range(m+1)]
        return self.backtrack(0,0,m,n,mat)
    
    def backtrack(self, r,c,m,n,mat):
        if r == m-1 and c == n-1:
            return 1
        if r>=m or c >= n:
            return 0
        if mat[r+1][c] == -1:
            mat[r+1][c] = self.backtrack(r+1,c,m,n,mat)
        if mat[r][c+1] == -1:
            mat[r][c+1] = self.backtrack(r,c+1,m,n,mat)
        return mat[r+1][c] + mat[r][c+1]

以上是top-down的DP解法。下面是更加直接的Bottom-Up的方法

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        mat = [[0 for j in range(n+1)] for i in range(m+1)]
        mat[m-1][n] = 1
        for i in range(m-1, -1, -1):
            for j in range(n-1,-1,-1):
                mat[i][j] = mat[i+1][j]+mat[i][j+1]
        return mat[0][0]

当然，这道题其实也是一个组合问题，就是从m+n-2个步骤中选择m-1步向下，或者选择n-1步向右

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        import math
        return math.factorial(m+n-2)/math.factorial(m-1)/math.factorial(n-1)