机器人从起点到终点有多少条不同的路径。仅仅能向右或者向下走。
注意点:
样例:
输入: m = 3, n = 7
输出: 28
非经常见的小学生奥数题,能够用排列组合来求解,一共要走 (m-1)+(n-1) 步。当中 (m-1) 步向下,(n-1)向右。且有公式
。那么能够用以下的代码求解:
- mCn = n!/m!(n-m)!
- import math class 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))
当然了,更常见的一种做法就是动态规划。要到达一个格子仅仅有从它上面或者左边的格子走过来,递推关系式:
。初始化条件是左边和上边都仅仅有一条路径。索性在初始化时把全部格子初始化为 1。
- dp[i][j]=dp[i-1][j]+dp[i][j-1]
- 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
欢迎查看我的 Github(https://github.com/gavinfish/LeetCode-Python) 来获得相关源代码。
来源: http://www.bubuko.com/infodetail-2231348.html