LeetCode解题之Unique Paths

原题

机器人从起点到终点有多少条不同的路径。仅仅能向右或者向下走。

unique-path

注意点：

格子大小最大为100*100

样例：

输入: m = 3, n = 7

输出: 28

解题思路

非经常见的小学生奥数题，能够用排列组合来求解，一共要走(m-1)+(n-1)步。当中(m-1)步向下，(n-1)向右。且有公式 mCn = n!/m!(n-m)! 。那么能够用以下的代码求解：

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

当然了，更常见的一种做法就是动态规划。要到达一个格子仅仅有从它上面或者左边的格子走过来，递推关系式：dp[i][j]=dp[i-1][j]+dp[i][j-1]。初始化条件是左边和上边都仅仅有一条路径。索性在初始化时把全部格子初始化为1。

AC源代码

class Solution(object):    def uniquePaths(self, m, n):        """        :type m: int        :type n: int        :rtype: int        """        dp = [[1 for __ in range(n)] for __ in range(m)]        for i in range(1, n):            for j in range(1, m):                dp[j][i] = dp[j - 1][i] + dp[j][i - 1]        return dp[m - 1][n - 1]if __name__ == "__main__":    assert Solution().uniquePaths(3, 7) == 28

欢迎查看我的()来获得相关源代码。

你可能感兴趣的文章