【Day 58 】2023-04-12 - 62. 不同路径

[azl397985856]

62. 不同路径

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/unique-paths/

前置知识

暂无

题目描述

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

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

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

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

 

示例 1:

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

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

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9

[JiangyanLiNEU]

• DP
• T = O(mn)
• S = O(mn)

  class Solution {
  public:
  int uniquePaths(int m, int n) {
      int dp[m][n];
      for (int row = 0; row < m; row++){
          for (int col = 0; col < n; col++){
              if (row == 0 || col == 0){
                  dp[row][col] = 1;
              }else {
                  dp[row][col] = dp[row-1][col]+dp[row][col-1];
              }
          }
      }
      return dp[m-1][n-1];
  }
  };

[Zoeyzyzyzy]

class Solution {
    // dp[i][j] 到达（i, j)有dp[i][j]条路径
    // dp[i][j] = dp[i-1][j] + dp[i][j-1]
    // 初始化：i = 0, j = 0 => 1
    // 遍历顺序：从上到下，从左到右
    // Time Complexity: O(m*n), Space Complexity: O(m*n)
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
        //利用滚动数组优化空间： 由于dp[i][j]仅依赖于上边和左边的元素
        public int uniquePaths1(int m, int n) {
            int[] dp = new int[n];
            Arrays.fill(dp, 1);
            //外层循环走一次，内层循环走一圈时，表示第一行第i列的总可能数
            //外层循环走2次，内层循环走两圈时，表示第2行第i列的总可能数
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    //“+=” is important! 说明一直在累加，内层循环为从左边加，外层循环再加为从上面加
                    dp[j] += dp[j - 1];
                }
            }
            return dp[n - 1];
        }
}

[JasonQiu]

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1 for _ in range(n)]] + [[1] + [0 for _ in range(n - 1)] for _ in range(m - 1)]
        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]

[lp1506947671]

class Solution:

    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] * n
        for _ in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j - 1]
        return dp[n - 1]

复杂度分析

• 时间复杂度：O(M * N)
• 空间复杂度：O(N)

[kofzhang]

思路

动态规划，令所有格子都初始化为1，从第二行第二列开始，dp[i][j]等于上面的格子值+左边的格子值 可以简化到一维进行累积。

复杂度

时间复杂度：O(mn) 空间复杂度：O(m or n)

代码

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1]*n
        for i in range(1,m):
            for j in range(1,n):
                dp[j]=dp[j]+dp[j-1]
        return dp[-1]

[bookyue]

TC: O(m*n)
SC: O(n)

    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                dp[j] = dp[j] + dp[j - 1];

        return dp[n - 1];
    }

[aoxiangw]

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        row = [1] * n
        for i in range(m - 1):
            new_row = [1] * n
            for j in range(n-2, -1, -1):
                new_row[j] = new_row[j + 1] + row[j]
            row = new_row
        return row[0]

time, space: O(mn), O(n)

[chanceyliu]

代码

function uniquePaths(m: number, n: number): number {
  const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
  for (let i = 0; i < m; i++) {
    f[i][0] = 1;
  }
  for (let j = 0; j < n; j++) {
    f[0][j] = 1;
  }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      f[i][j] = f[i - 1][j] + f[i][j - 1];
    }
  }
  return f[m - 1][n - 1];
}

复杂度分析

• 时间复杂度：O(mn) m 和 n 是第一个和第二个参数
• 空间复杂度：O(mn)

[airwalkers]

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == 1 && j == 1) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}

[Diana21170648]

思路

二维动态规划，排列组合

class Slution:
    def uniquepaths(self,m:int,n:int)->int:
        dp=1*[n]
        for _ in range(1,m):
            for j in  range(1,n):
                dp=dp[j-1]
                return dp[n-1]

**复杂度分析**
- 时间复杂度：O(m*n)，双重循环
- 空间复杂度：O(n)，只考虑上面和左边的元素

[Meisgithub]

class Solution {
public:
    int uniquePaths(int m, int n) {
        // vector<vector<int>> dp(m, vector<int>(n, 0));
        // dp[0][0] = 1;
        // for (int i = 0; i < m; i++)
        // {
        //     for (int j = 0; j < n; j++)
        //     {
        //         if (i > 0)
        //         {
        //             dp[i][j] += dp[i - 1][j];
        //         }
        //         if (j > 0)
        //         {
        //             dp[i][j] += dp[i][j - 1];
        //         }
        //     }
        // }
        // return dp[m - 1][n - 1];

        vector<int> dp(n, 0);
        dp[0] = 1;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                // int tmp = dp[j];
                if (j > 0)
                {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return dp[n - 1];
    }
};

[Abby-xu]

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        @cache
        def dfs(i, j):
            if i >= m or j >= n:      return 0
            if i == m-1 and j == n-1: return 1
            return dfs(i+1, j) + dfs(i, j+1)
        return dfs(0, 0)

[csthaha]

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    // 二维 爬楼梯。dp[i, j] = dp[i -  1, j] + dp[i, j. -1];
    if(m === 0 && n === 0) return 0;
    // 用于记忆
    const array = new Array(m).fill(new Array(n).fill(0));

    // 第一行、第一列 都只有一种路径。
    for(let i = 0; i < m; i++) {
        array[i][0] = 1;
    }
    for(let j = 0; j < n; j++) {
        array[0][j] = 1;
    }

    for(let i = 1; i < m; i++) {
        for(let j = 1; j < n; j++) {
            array[i][j] = array[i - 1][j] + array[i][j - 1];
        }
    }
    return array[m - 1][n - 1]
};

[zhangyu1131]

class Solution {
public:
    int uniquePaths(int m, int n) {
        // 动态规划
        vector<int> dp(n, 1);
        for (int i = 1; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (j == 0)
                {
                    dp[j] = 1;
                }
                else
                {
                    dp[j] = dp[j - 1] + dp[j];
                }
            }
        }

        return dp[n - 1];
    }
};

[FireHaoSky]

思路：动态规划 dp[i][j] = dp[i-1][j] + dp[i][j-1]

代码：python

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1]*n] + [[1]+[0]*(n-1) for _ in range(m-1)]
        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(nm)
空间复杂度：O(nm)
"""

[harperz24]

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]

        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]

        # dp 2d
        # time: O(m * n)
        # space: O(m * n)

[Hughlin07]

class Solution {

public int uniquePaths(int m, int n) {
    int dp[][] = new int[m][n];
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(i == 0 || j == 0){
                dp[i][j] = 1;
            }
            else{
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }
    return dp[m-1][n-1];
}

}

[kangliqi1]

class Solution:

def uniquePaths(self, m: int, n: int) -> int:
    dp = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]
    return dp[n - 1]

[LIMBO42]

class Solution {
public:
    int uniquePaths(int m, int n) {
        // dp[i][j] = dp[i-1][j] + dp[i][j-1]
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for(int i = 1; i <= m; ++i) {
            dp[i][1] = 1;
        }
        for(int i = 1; i <= n; ++i) {
            dp[1][i] = 1;
        }
        for(int i = 2; i <= m; ++i) {
            for(int j = 2; j <= n; ++j) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }
};

[Jetery]

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector(n, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
};

[Lydia61]

62. 不同的路径

思路

数学方法，排列组合

代码

from math import factorial as f
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return f(m + n - 2) // f(m - 1) // f(n - 1)

复杂度分析

• 时间复杂度：O(m-n)
• 空间复杂度：O(1)

[NorthSeacoder]

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    //dp[i][j]到达 点[i,j]的路径数;
    let dp = new Array(m).fill(1).map(() => new Array(n).fill(1));
    //dp[i][j] = dp[i-1][j]+dp[i][j-1];
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

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

[wangzh0114]

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> f(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            f[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            f[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
};

[huizsh]

func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([]int, n)
        for j := 0; j < n; j++ {
            if i == 0 || j == 0 {
                dp[i][j] = 1
            } else {
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            }
        }
    }
    return dp[m-1][n-1]
}

[RestlessBreeze]

code

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> temp(n, 1);
        vector<vector<int>> dp(m, temp);

        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

[X1AOX1A]

class Solution:

    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] * n
        for _ in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j - 1]
        return dp[n - 1]

[sye9286]

代码

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    const dp = new Array(m).fill(0).map(() => new Array(n).fill(0));
    for (let i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (let j = 0; j < n; j++) {
        dp[0][j] = 1;
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
};

复杂度分析

• 时间复杂度：O(mn)
• 空间复杂度：O(mn)

[joemonkeylee]

思路

dp

代码

      public int UniquePaths(int m, int n)
        {
            int[][] dp = new int[m][];
            for (int i = 0; i < m; i++)
            {
                dp[i] = new int[n];
            }
            dp[0][0] = 1;
            for (int j = 1; j < n; j++)
            {
                dp[0][j] = 1;
            }
            for (int i = 1; i < m; i++)
            {
                dp[i][0] = 1;
            }
            for (int i = 1; i < m; i++)
            {
                for (int j = 1; j < n; j++)
                {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
            return dp[m - 1][n - 1];
        }

复杂度分析

• 时间复杂度：O(mn)
• 空间复杂度：O(mn)

[wwewwt]

思路

因为机器人只能向右或向下移动，所以到每一格的路线条数只能是它上面一格的条数加它左边一格的条数

代码

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        #二维数组

        l = 0 #行从0开始
        mat = [] # 定义一个二维数组mat
        while l < m:
            r = 0 #列从0开始
            line = [] #line存储每一行数据
            while r < n:
                line.append(0) #装载行数据
                r = r + 1
            mat.append(line) #按行装载二维数组
            l = l + 1

        #初始化行和列
        for i in range(m):
            for j in range(n):
                if i == 0 or j ==0:
                    mat[i][j] = 1
                else:
                    mat[i][j] = mat[i-1][j] + mat[i][j-1]

        return mat[m-1][n-1] 

复杂度

时间复杂度O(mn) 空间复杂度O(mn)

[jmaStella]

思路

二维爬了楼梯 dp

代码

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i=0; i<m;i++){
            dp[i][0] = 1;
        }
        for(int j=0; j<n; j++){
            dp[0][j] = 1;
        }
        for(int i=1; i<m;i++){
            for(int j=1; j<n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

复杂度

时间 O(MN) 空间 O(MN)

[snmyj]

class Solution {
public:
    int uniquePaths(int m, int n) {
       vector<vector<int>> dp(m,vector<int>(n));
       for(int i=0;i<n;i++) dp[0][i]=1;
       for(int j=0;j<m;j++) dp[j][0]=1;
       for(int i=1;i<m;i++){
           for(int j=1;j<n;j++){
               dp[i][j]=dp[i][j-1]+dp[i-1][j];
           }
       }
       return dp[m-1][n-1];
    }
};

[yingchehu]

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        d = [[1] * n for _ in range(m)]

        for col in range(1, m):
            for row in range(1, n):
                d[col][row] = d[col - 1][row] + d[col][row - 1]

        return d[m - 1][n - 1]

[Fuku-L]

代码

class Solution {
    public int uniquePaths(int m, int n) {
        int[] cur = new int[n];
        Arrays.fill(cur,1);
        for (int i = 1; i < m;i++){
            for (int j = 1; j < n; j++){
                cur[j] += cur[j-1] ;
            }
        }
        return cur[n-1];
    }
}

复杂度分析

• 时间复杂度：O(N*M)。
• 空间复杂度：O(N)