azl397985856 commented 2 years ago

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

yetfan commented 2 years ago

思路第一行和第一列都只有1种可能，其余位置，均为上面一个格子+左边一个格子的路径和。

代码

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

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

思路以行为单位，一批批更新。从而压缩数组。每个格子dp[j] 为上一行格子位置dp[j] + 左边格子dp[j-1]的路径和。

代码

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-1]
        return dp[n-1]

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

xinhaoyi commented 2 years ago

62. 不同路径

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

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

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

示例

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

向右 -> 向下 -> 向下
向下 -> 向下 -> 向右
向下 -> 向右 -> 向下

思路一：DFS递归

DFS递归写法

m是行，n是列

我假设机器人起点坐标是(0,0),那么终点就是(m - 1, n -1)

我们将dp[x,y]定义为处在x,y坐标时，共有多少种路径可以到到达finish终点

显然dp[x,y] = dp[x+1,y] + dp[x,y+1]，即向下走的可能性之和 + 向右走的可能性之和

出口条件是x == m ,或者 y == n, 此时dp[x,y] = 0, 因为越界了

代码

class Solution {
    public int uniquePaths(int m, int n) {
        //m是行，n是列
        //我假设机器人起点坐标是(0,0),那么终点就是(m - 1, n -1)
        //我们将dp[x,y]定义为处在x,y坐标时，共有多少种路径可以到到达finish终点
        //显然dp[x,y] = dp[x+1,y] + dp[x,y+1]，即向下走的可能性之和 + 向右走的可能性之和
        //出口条件是x == m ,或者 y == n, 此时dp[x,y] = 0, 因为越界了
        return iterationImproved(0, 0, m, n);

    }
    //这种写法超时了
    public int iteration(int x, int y, int m, int n){
        //越界dp = 0
        if(x == m || y == n){
            return 0;
        }

        //到达终点dp = 1，因为从终点出发到终点，就一种可能的情况
        if(x == m-1 && y == n-1){
            return 1;
        }

        return iteration(x + 1, y, m, n) + iteration(x, y + 1, m, n);
    }

}

这种写法因为重复计算了太多次，所以是会超时的！！

如下图：

复杂度分析

时间复杂度：$O(MN)$

空间复杂度：$O(MN)$

思路二：思路一改进

思路一改进！！缩短运行时间

参考题解

三种实现+详细图解 62. 不同路径 - 不同路径 - 力扣（LeetCode） (leetcode-cn.com)

我们引入一个cache缓存Map，把已经遍历过的(x,y)保存起来，下次碰见了直接调用，避免重复计算，然后只要碰到边界就只剩下唯一一条通往finish的路了，所以直接return 1.

怎么引入缓存，我们介绍一下抽象类Pair，Pair是一个这样的结构（leftValue,rightValue)，只要左右元素都相等，我们就可以得出两个Pair对象的equals方法是true，即两个Pair值相等。竟然引申出，只要Pair p = new Pair(i,j);然后cache.containsKey(p)，因为两个不同的pair对象，只要值相等，他们就被认为是相等的，所以containsKey(p)会返回true，我们就可以知道这个(x,y)是以前被计算过了的，并存在了cache中

Pair的讲解可以看看这个博客

(13条消息) （二十六）Java组件类Pair、MutablePair、ImmutablePair详解_明洋的专栏-CSDN博客_immutablepair

代码

//方法二
class Solution {
    public int uniquePaths(int m, int n) {
        Map<Pair<Integer,Integer>,Integer> cache = new HashMap();
        return iteration(cache,0,0,m,n);
    }
    public int iteration(Map<Pair<Integer,Integer>,Integer> cache,int x, int y, int m, int n){
        //先看一看cache里面有没有
        Pair pair = new Pair(x,y);
        //要是有，直接返回缓存值
        if(cache.containsKey(pair)){
            return cache.get(pair);
        }
        //到边界了
        if(x == m - 1 || y == n - 1){
            return 1;
        }
        //没遍历过这个结点，先缓存到cache中，再dp[x,y] = dp[x+1,y] + dp[x,y+1]
        cache.put(pair, iteration(cache, x + 1, y, m, n) + iteration(cache, x, y + 1, m, n));
        return cache.get(pair);
    }
}

复杂度分析

时间复杂度：$O(MN)$

空间复杂度：$O(MN)$

思路三：动态规划

参考题解

三种实现+详细图解 62. 不同路径 - 不同路径 - 力扣（LeetCode） (leetcode-cn.com)

动态规划的思路和前面思路一的dfs递归其实是反着来的，怎么到达终点(m,n)？要么是从(m-1,n)出发，要么是从(m,n-1)出发

不管从哪条路出发都只有一种可能性（一条路径）到达target点

所以dp[m,n] = dp[m-1,n] + dp[m,n-1]

进而推广到状态转移方程

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

递归的边界条件是走到了最右边一列、或者是走到了最下面一行。动态规划正好是反过来的，因为我们是从上到下一行一行推导的。所以我们要处理下第一行和第一列，将它们都赋予1即可。

代码

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        //第一行都赋予 1
        for(int i = 0; i < m; ++i) {
            dp[i][0] = 1;
        }
        //第一列都赋予 1
        for(int j = 0; j < n; ++j) {
            dp[0][j] = 1;
        }
        //两个for循环推导，对于(i,j)来说，只能由上方或者左方转移过来
        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(m*n)$

空间复杂度：$O(m*n)$

zwx0641 commented 2 years ago

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];
}

}

laofuWF commented 2 years ago

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

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

        return dp[-1][-1]

ZacheryCao commented 2 years ago

Idea

Dynmaic Programming

Code

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

Complexity:

Time: O(M *N) Space: O(N)

zhangzz2015 commented 2 years ago

思路

采用dp方法，定义dp[i][j]为到[i][j]位置的路径数， dp[i][j] = dp[i-1][j] + dp[i][j-1]，时间复杂度为O(n m)，空间复杂度为O(n m)，也可压缩到1维。

关键点

代码

语言支持：C++

C++ Code:


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=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(i==0 && j==0)
                   dp[i+1][j+1] = 1; 
                else    
                   dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1];  
            }
        }

        return dp[m][n]; 

    }
};;

CoreJa commented 2 years ago

思路

纯属练手多写了几个写法。以下复杂度除纯DFS外均为$O(mn)$

DFS：写着玩，直接超时，复杂度$O(m!n!)$
DFS+记忆化：过
DP
排列组合：math.comb

代码

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

        return dfs(m - 1, n - 1)

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

        def dfs(i, j):
            if dp[i][j] != -1:
                return dp[i][j]
            if i <= 0 or j <= 0:
                return 1
            dp[i][j] = dfs(i - 1, j) + dfs(i, j - 1)
            return dp[i][j]

        return dfs(m - 1, n - 1)

    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[-1][-1]

    def uniquePaths4(self, m: int, n: int) -> int:
        return math.comb(m - 1 + n - 1, m - 1)

JudyZhou95 commented 2 years ago

代码

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[-1][-1]

复杂度

TC: O(MN) SC: O(MN)

zjsuper commented 2 years ago

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        ans = [[0]*n]*m
        for i in range(m):
            for j in range(n):
                if i==0 and j==0:
                    ans[i][j] =1
                elif i==0 and j!=0:
                    ans[i][j] = ans[i][j-1]
                elif i!=0 and j==0:
                    ans[i][j] = ans[i-1][j]
                else:
                    ans[i][j] = ans[i-1][j]+ans[i][j-1]
        return ans[m-1][n-1]

cszys888 commented 2 years ago

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

time complexity: O(m*n) space complexity: O(min(m,n))

falconruo commented 2 years ago

思路:

动态规划

复杂度分析: 方法一

时间复杂度: O(M * N)，M, N为grid的大小
空间复杂度: O(M * N), 二维数组空间

代码(C++):


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

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && j > 0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                else
                    dp[i][j] = 1;
            }
        }

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

ginnydyy commented 2 years ago

Problem

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

Notes

DP problem
Need to figure out the relation between the sub problems, since there are only two ways to move, we can define the dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
Since there is at least one way to go to any cell, so we can initiate the dp array with value 1.

Solution

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int[] array: dp){
            Arrays.fill(array, 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];
    }
}

Complexity

Time: O(m n), m and n is the dimension of the board, there are m n cells, we need to iterate each cell, for each cell, it costs O(1).
Space: O(m * n) extra space is required for the dp array to store the status.

feifan-bai commented 2 years ago

思路 1.DP

代码

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m == 1 or n == 1:
            return 1
        return self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1)

复杂度分析

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

wangzehan123 commented 2 years ago

Java Code:


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];
    }
}

tongxw commented 2 years ago

思路

dp(i, j) = dp(i-1, j) + dp(i, j-1)

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];
    }
}

TC: O(mn) SC: O(mn)

moirobinzhang commented 2 years ago

Code:

public int UniquePaths(int m, int n) {
    int[,] dp = new int[m, n];
    dp[0, 0] = 0;

    for (int i = 0; i < m; i++)
        dp[i, 0] =  1;

    for (int i = 0; i < n; i++)
        dp[0, i] = 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];
}

yan0327 commented 2 years ago

func uniquePaths(m int, n int) int {
    dp := make([][]int,m)
    for i := range dp{
        dp[i] = make([]int,n)
        if i == 0{
            for j:=0;j<len(dp[0]);j++{
                dp[0][j] = 1
            }
        }
    }
    for i:=0;i<m;i++{
        dp[i][0] = 1
    }
    for i:=1;i<m;i++{
        for 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）

xuhzyy commented 2 years ago

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 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[-1][-1]

Tesla-1i commented 2 years ago

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[-1][-1]

ivangin commented 2 years ago

code:

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

wdwxw commented 2 years ago

class Solution { public int uniquePaths(int m, int n) { int[][] f = new int[m][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]; } }

charlestang commented 2 years ago

思路

动态规划。设 dp(i, j) 代表，走到座标 i, j 的方法数。则 dp(i,j) = dp(i - 1, j) + dp( i, j - 1)。

时间复杂度 O(mn)

空间复杂度 O(mn)

代码

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]

haixiaolu commented 2 years ago

思路

DP

从后往前遍历
倒数第一行设置为1
倒数第二行等于倒数第一行的值加上右边的值，一次类推
等到开始的点，就是我们想要的答案

代码/ python

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        row = [1] * n

        for i in range(m - 1): # going to each row except the last row
            newRow = [1] * n
            for j in range(n - 2, -1, -1): # reverse order
                newRow[j] = newRow[j + 1]  + row[j]
            row = newRow

        return row[0]

复杂度分析

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

linyang4 commented 2 years ago

思路

动态规划

base case: dp[0][j] = dp[i][0] = 1
状态转移方程: dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

代码(JavaScript)

var uniquePaths = function(m, n) {
    const dp = new Array(m).fill(1).map(() => new Array(n).fill(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)

wenlong201807 commented 2 years ago

代码块


var uniquePaths = function (m, n) {
  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(n)
空间复杂度 O(1)

GaoMinghao commented 2 years ago

思路

到点（a,b)的路线数目由它上面的点（a-1,b）和左边的点（a,b-1) 相加得到，因为只可以从左边或者上面来，最左边一列和最上面一列，都只有一个方向，因此作为基本case，路线为1

代码

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 i = 0; i<n;i++)
            dp[0][i] = 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(m*n)

mannnn6 commented 2 years ago

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 i = 0; i<n;i++)
            dp[0][i] = 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];
    }
}

callmeerika commented 2 years ago

思路

动态规划

代码

var uniquePaths = function (m, n) {
    let dp = new Array(m + 1).fill(0).map(vv => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
      for (let 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];
  };

复杂度

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

z1ggy-o commented 2 years ago

思路

今天的题目取巧了。因为是经典题目，所以已经知道了是使用 DP 来解决。

题目的转移方程也很简单，我觉得是最简单的，比爬楼梯还直观。

代码

CPP

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

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

复杂度分析

时间：O(mn)
空间：O(mn)

RocJeMaintiendrai commented 2 years ago

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

Alexno1no2 commented 2 years ago

# 思路
# 1.定义状态：不同路径的数量 dp[i][j]：到位置(i, j)一共有几条路径
# 2.初始化状态：初始化第一行和第一列，均为1
# 3.状态转移：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

# 复杂度分析

# 时间复杂度：O(m * n)O(m∗n)
# 空间复杂度：O(m * n)O(m∗n)

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

declan92 commented 2 years ago

思路

dp[i][j]:到达nums[i][j]的不同路径数;
dp[i][j] = dp[i-1][j] + dp[i][j-1],注意不要越界;
dp[0][0] = 1;

双循环遍历 java code

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] = dp[i][j-1];
            }else if(i!=0&&j==0){
                dp[i][j] = dp[i-1][j];
            }else 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];
}
}

时间:$O(mn)$ 空间:$O(mn)$

tangjy149 commented 2 years ago

思路

dp存储的是到达该位置的路径数目，又因为只能向下或向右，因此每个点的方案=上一个+左一个的和

代码

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(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];
    }
};

zwang2244 commented 2 years ago

思路

dp

Unique path to (m,n) = Unique path to (m-1,n) + Unique path to (m,n-1)

代码

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 row = 1; row < m; row++){
            for(int col = 1; col < n; col++){
                dp[row][col] = dp[row-1][col] + dp[row][col-1];
            }
        }
        return dp[m-1][n-1];
    }
}

复杂度分析

时间复杂度：O(N*M)，其中 N 为数组长度。
空间复杂度：O(N*M)

Hacker90 commented 2 years ago

class Solution { public: int uniquePaths(int m, int n) { vector<vector >dp(m,vector(n));//定义二维数组swp[][]，n行 m列 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];
} };

anyingbinglong commented 2 years ago

思路 dp

Unique path to (m,n) = Unique path to (m-1,n) + Unique path to (m,n-1)

代码 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 row = 1; row < m; row++){ for(int col = 1; col < n; col++){ dp[row][col] = dp[row-1][col] + dp[row][col-1]; } } return dp[m-1][n-1]; } } 复杂度分析

时间复杂度：O(NM)，其中 N 为数组长度。空间复杂度：O(NM)

Myleswork commented 2 years ago

思路

dp

转移方程：dp[i] = dp[i-1] [j]+dp[i] [j-1]

代码

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m==1&&n==1) return 1;
        vector<vector<int>> dp(m,vector<int>(n,0));
        for(int i = 1;i<n;i++){
            dp[0][i] = 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(m*n)

空间复杂度：O(m*n)

1149004121 commented 2 years ago

不同路径

思路

动态规划。

代码

var uniquePaths = function(m, n) {
    let dp = new Array(n).fill(1);
    for(let i = 1; i < m; i++){
        for(let j = 1; j < n; j++){
            dp[j] = dp[j] + dp[j - 1];
        }
    }
    return dp[n - 1];
};

复杂度分析

时间复杂度：O(NM)。
空间复杂度：O(N)。

LannyX commented 2 years ago

思路

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)

zhiyuanpeng commented 2 years ago

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

Richard-LYF commented 2 years ago

class Solution: def uniquePaths(self, m: int, n: int) -> int: a = min(m,n) b = max(m,n)

    k = [1] * a

    for i in range(b - 1):
        for j in range(a - 1):
            k[j + 1] = k[j+1] + k[j]

    return k[-1]

Toms-BigData commented 2 years ago

【Day 58】62. 不同路径

思路

二维dp换皮

golang代码

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

复杂度

时间:O(nm) 空间:O(nm)

CodingProgrammer commented 2 years ago

思路

DP

代码

class Solution {
    public int uniquePaths(int m, int n) {
        // dp[i][j] 表示到达 (i,j) 位置的路径数量
        // dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        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];
    }
}

复杂度

Time : O(M*N)
Space: O(M*N)

alongchong commented 2 years ago

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

ZJP1483469269 commented 2 years ago

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

        for i in range(1,m + 1):
            for j in range(1,n + 1):
                if i == 1 and j == 1:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]

        return dp[m][n]

iambigchen commented 2 years ago

思路

动态规划，dp[i][j] = dp[i-1][j] + dp[i][j-1]

关键点

代码

语言支持：JavaScript

JavaScript Code:


/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    const dp = Array(m).fill(1).map(() => new Array(n).fill(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];
};

复杂度分析

令 n 为数组长度。

时间复杂度：$O(m*n)$
空间复杂度：$O(m*n)$

jiaqiliu37 commented 2 years ago

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1]*n for i 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]

Time complexity Space complexity O(mn)

Menglin-l commented 2 years ago

approach: dynamic programming

code:

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{
                if(i != 0) f[i][j] += f[i - 1][j]; 
                if(j != 0) f[i][j] += f[i][j - 1]; 
            }
        return f[m - 1][n - 1];
    }
}

complexity:

Time: O(M * N)

Space: O(M * N)

zol013 commented 2 years ago

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        ''''
        memo = {}

        def recursion(row, col):
            if row == 1 or col == 1:
                memo[(row, col)] = 1
                return 1
            if (row ,col) in memo:
                return memo[(row, col)]

            memo[(row - 1, col)]  = recursion(row - 1, col)
            memo[(row, col - 1)] = recursion(row, col - 1)

            return memo[(row - 1, col)] + memo[(row, col - 1)]

        return recursion(m, n)
        '''

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

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

hdyhdy commented 2 years ago

思路;动态规划，第一行和第一列都只有1种可能，其余位置，均为上面一个格子+左边一个格子的路径和。

func uniquePaths(m, n int) int {
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
        dp[i][0] = 1
    }
    for j := 0; j < n; j++ {
        dp[0][j] = 1
    }
    for i := 1; i < m; i++ {
        for 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）

leetcode-pp / 91alg-6-daily-check

【Day 58 】2022-02-07 - 62. 不同路径 #68

62. 不同路径

入选理由

题目地址

前置知识

题目描述

62. 不同路径

思路一：DFS递归

代码

复杂度分析

思路二：思路一改进

代码

复杂度分析

思路三：动态规划

代码

复杂度分析

Idea

Code

Complexity:

思路

关键点

代码

思路

代码

代码

复杂度

Problem

Notes

Solution

Complexity

思路

code:

思路

代码

思路

代码/ python

复杂度分析

思路

动态规划

代码(JavaScript)

复杂度

代码块

时间复杂度和空间复杂度

思路

代码

时间复杂度

思路

代码

复杂度

思路

代码

思路

代码

思路

代码

思路

代码

思路

代码

【Day 58】62. 不同路径

思路

golang代码

复杂度

思路

代码

复杂度

思路

关键点

代码

approach: dynamic programming

code:

complexity:

Time: O(M * N)

Space: O(M * N)