62. DP Unique Paths
相当于机器人总共走了m + n - 2步,其中m - 1步向下走,n - 1步向右走,那么总共不同的方法个数就相当于在步数里面m - 1和n - 1中较小的那个数的取法,实际上是一道组合数的问题,写出代码如下:
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
mi = min(m-1,n-1)
ma = max(m-1,n-1)
fenzi = 1
fenmu = 1
for i in range(1,mi+1):
fenmu *= i
fenzi *= ma+mi+1-i
return fenzi/fenmu
方法二
递推式 res[i][j]表示到当前位置不同的走法的个数
res[i][j]=res[i-1][j]+res[i][j-1]
dp 过程 对每行每个格子进行扫描,对于空间可以看出我们每次只需要用到上一行当前列,以及前一列当前行的信息,我们只需要用一个一维数组存上一行的信息即可
class Solution:
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
dp = [0]*n
dp[0] = 1
for i in range(m):
for j in range(1,n):
dp[j] += dp[j-1]
return dp[-1]