机器人需要走多少步呢？

大家好，我是程序员学长~

如果喜欢，记得点个关注哟~

问题描述

示例：

输入：m = 3，n = 2

输出：3

解释：从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

分析问题

下面我们来看一下代码如何实现。

class Solution:
    def uniquePaths(self,m ,n):
        #申请一个m行n列的矩阵，赋值为1
        dp = [[1 for _ in range(n)] for _ in range(m)]
        #填充矩阵dp
        for i in range(1,m):
            for j in range(1,n):
                #根据状态转移方程，填充矩阵
                dp[i][j] = dp[i-1][j] + dp[i][j-1]

        return dp[m-1][n-1]

该算法的时间复杂度和空间复杂度都是O(m*n)。

优化

Tips: C(n,m)=n * (n-1) ... (n-m+1) (m * (m-1) * (m-2) ... * 1) 

class Solution:
    def uniquePaths(self,m ,n):
        #一共n+m-2步
        #C(n,m)= n * (n-1) *...* (n-m+1) / (m * (m-1) * (m-2) ... * 1)
        count = n + m - 2
        #选择n-1步向右走
        k = n - 1
        num = 1.0
        for i in range(1,k+1):
            num=num * (count - k + i ) / i
        return int(num)

啰嗦一句

今天我们就聊到这里，如果喜欢，记得给个三连吧~

欢迎加我个人微信，这里不仅有算法知识，你想要的都在这里~

你知道的越多，你的思维越开阔。我们下期再见~