美文网首页
Unique Paths

Unique Paths

作者: 穿越那片海 | 来源:发表于2017-09-03 17:14 被阅读0次

    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)
    

    相关文章

      网友评论

          本文标题:Unique Paths

          本文链接:https://www.haomeiwen.com/subject/zjrjjxtx.html