高频算法题之求路径

求路径

读前福利，送大家一些电子书

62. 不同路径

问题描述

一个机器人在 m×n 大小的地图的左上角（起点）。机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。可以有多少种不同的路径从起点走到终点？

示例：

输入：m = 3，n = 2
输出：3
解释：从左上角开始，总共有 3 条路径可以到达右下角。

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

分析问题

根据题意，由于机器人只能选择往下走或者往右走，所以对于右下角位置matrix[m-1] [n-1]来说，它可以由该位置的上面向下走，即从matix[m-2] [n-1] 向下走 ，也可以由该位置的左边向右走，即从matrix[m-1] [n-2] 向右走。

我们定义一个m*n的矩阵dp，其中dp[i] [j]表示从起点到达第i行第j列的方案数。根据前面的分析，我们可以清楚的知道，dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]。所以，我们可以采用动态规划思想来求解，其状态转移方程为 dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]。

对于第一行的元素来说，我们只有一种走法，即只能从左边位置向右走；对于第一列元素来说，也只有一种走法，只能从上边位置向下走。

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

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)。

优化

我们知道，从左上角移动到右下角，一共需要走m-1+n-1步，其中包含m-1步向下，n-1步向右。由于只能向下或者向右走，所以当我们从这m+n-2步中选择m-1次向下走，则剩下的n-1步只能向右走（或者选其中的n-1步向右走，剩下的m-1步只能向下走），所有总的方案数为 C(m+n-2, m-1)或者C(m+n-2, n-1)，没错，这就是数学上的排列组合问题。

**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)