LeetCode—— 不同路径

题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:

输入: m = 7, n = 3
输出: 28

一、CPP

1. 动态规划法：

解题思路:详解异步动态规划笔记——类型二：计数型。

时间复杂度:O(n²)。
空间复杂度:O(1)。

class Solution {
public:
    int uniquePaths(int m, int n) {

        //开辟二维数组保存状态:因为最后为(m-1,n-1)，所以数组大小为m*n，不用再行列加1
        int f [m][n];

        for(int i=0; i<m; i++){              //从上到下
            for(int j=0; j<n; j++){
                if(i==0 || j==0){            //从左到右
                    //出口:边界条件
                    f[i][j] = 1;
                }
                else{
                    //更新(i,j)位置的状态:可以使用加法来分别表示两个方向的更新（上和左）
                    f[i][j] = f[i-1][j] + f[i][j-1];
                }
            }
        }

        return f[m-1][n-1];
        
    }
};

2. 递归法：

解题思路:由于只能向左和向下走，所以走到(m,n)这个问题可以分解成走到(m-1,n)和(m,n-1)这两个子问题，边界条件就是当m=1或n=1时返回1.因为沿着两个“墙壁”走只能是向下或向左一种可能。

• 注意：递归法范围为1～m，1～n。上面的动态规划使用的二维数组来保存状态，范围为1～m-1，1～n-1。

时间复杂度:O(n²)。
空间复杂度:O(1)。

class Solution{
    public:
        int uniquePaths(int m, int n){
            if(m <= 0 || n <= 0){
                return 0;
            }
            //只能一直向右走或者一直向下走，所以路径数为 1
            if(m == 1  || n == 1){
                return 1;
            } 
                
            int paths = 0;
            paths += uniquePaths(m-1,n) + uniquePaths(m,n-1);
            return paths;
        }
};

这是递归的方法会超时：

原因是递归时进行了很多重复的计算：比如使用递归计算7×３时

所以使用动态规划的思想保存中间计算的结果。

二、Java（动态规划）

class Solution {
    public int uniquePaths(int m, int n) {
        //存放状态
        int [][] f= new int[m][n];

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){

                if(i==0 || j==0){
                    f[i][j] = 1;
                }
                else{
                    f[i][j] = f[i-1][j] + f[i][j-1];
                }

            }
        }
        return f[m-1][n-1];        
    }
}

三、Python（动态规划）

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        # 初始化二维列表
        f = [[0] * n] * m

        for i in range(m):
            for j in range(n):
                if i==0 or j==0:
                    f[i][j] = 1
                else:
                    f[i][j] = f[i-1][j] + f[i][j-1]
        return f[m-1][n-1]

四、各语言及算法时间复杂度