62-动态规划

2020-08-01

Leetcode题解

动态规划

题目重点是：1、机器人只能向右或向下走；2、机器人一定在左上角，目标一定在右上角。因此，机器人一定要走m+n-2步，并且必须向下走n-1步、向右走m-1步。将问题可转换为排列组合问题。

根据公式，即可完成，(n-m)!代入本题的值，化简等于(m-1)!

1
2
3

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return int(math.factorial(n+m-2)/(math.factorial(n-1)*math.factorial(m-1)))