azl397985856 commented 3 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

yanglr commented 3 years ago

思路:

动态规划。

这个题属于dp问题之求方案总数量类。

dp数组

dp[i][j]: 从位置(0, 0)走到位置(i, j)的unique path的数量。

原点位置(0, 0)只有不动这一种走法, 故有: dp[0][0] = 1

根据规则, 机器人每次只能向下或者向右移动一步, 故对矩阵中间某个位置(i, j), 如果要能到达这个位置, 那么机器人上一个位置必然为位置(i-1, j) 或 (i, j-1)。于是有: dp[i][j] = dp[i-1][j] + dp[i][j-1]

已AC的C++代码:

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[m][n]; // dp数组 - dp[i][j]: 从位置(0, 0)走到位置(i, j)的unique path的数量
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1; /* 原点位置(0, 0)只有不动这一种走法, 对矩阵中间某个位置 dp[i][j] = dp[i-1][j] + dp[i][j-1] */
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i >= 1) 
                    dp[i][j] += dp[i-1][j];
                if (j >= 1)
                    dp[i][j] += dp[i][j-1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

复杂度分析

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

for123s commented 3 years ago

思路

关键点

代码

语言支持：C++

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

复杂度分析

令 n 为数组长度。

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

xj-yan commented 3 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];
    }
}

Time Complexity: O(m n), Space Complexity: O(m n)

fzzfgbw commented 3 years ago

思路

dp

代码

public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        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(m*n)
空间复杂度：O(m*n)

yachtcoder commented 3 years ago

O(mn), O(mn)

class Solution:
    def uniquePaths(self, M: int, N: int) -> 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]

JiangyanLiNEU commented 3 years ago

Idea

there are only two ways to reach cell: from i-1, j or i, j-1
so we use an array of arrays to record the number of path we can reach this spot

Runtime = Space = O(m*n)

Python

class Solution(object):
def uniquePaths(self, m, n):
    path_to_this = [[0 for i in range(n)] for j in range(m)]
    path_to_this[0][0] = 1
    for j in range(1, n):
        path_to_this[0][j] = 1
    for i in range(1, m):
        path_to_this[i][0] = 1

    for i in range(1,m):
        for j in range(1,n):
            path_to_this[i][j] = path_to_this[i-1][j] + path_to_this[i][j-1]
    return path_to_this[-1][-1]

JavaScript

var uniquePaths = function(m, n) {
let path_to_this = [];
for (let i=0; i<m; i++){
    path_to_this.push([]);
    for (let j=0; j<n; j++){
        path_to_this[i].push(i=== 0 || j===0 ? 1: 0);
    };
};
for (let i=1; i<m; i++){
    for (let j=1; j<n; j++){
        path_to_this[i][j] = path_to_this[i-1][j] + path_to_this[i][j-1];
    };
};
return path_to_this[m-1][n-1];    
};

florenzliu commented 3 years ago

Explanation

dp[i][j]: the total number of unique paths to reach cell[i][j]
to reach cell[i][j], its last step is either from the left or from the top: dp[i][j] = dp[i-1][j] + dp[i][j-1]

Python

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][j-1] + dp[i-1][j]
        return dp[-1][-1]

Complexity:

Time Complexity: O(mn)
Space Complexity: O(mn)

heyqz commented 3 years ago

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

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

biancaone commented 3 years ago

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

        dp = [[0 for _ in range(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[m - 1][n - 1]

erik7777777 commented 3 years ago

public int uniquePaths(int m, int n) {
        int[] col = new int[n];  // do the state compression
        Arrays.fill(col, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                col[j] = col[j] + col[j - 1];  // col[j] means answer from left, col[j - 1] means answer from up 
            }
        }
        return col[n - 1];
    }

time O(m * n) space O(n)

st2yang commented 3 years ago

思路

dp 滚动数组

代码

python

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[i][j] = dp[i-1][j] + dp[i][j-1]
            dp[j] += dp[j-1]

    return dp[n-1]

复杂度

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

Daniel-Zheng commented 3 years ago

思路

动态规划。

代码(C++)

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

复杂度分析

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

ysy0707 commented 3 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 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)

mixtureve commented 3 years ago

代码

语言支持：Java

Java Code:


time: O(m * n)  space : O(n)
class Solution {
    public int uniquePaths(int m, int n) {
        // use DP 
        // DP[i][j]: the possible ways to reach grid[i][j]
        // i - 1, j &  i, j - 1

        int[] dp = new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) { // 在左右边界上一位着只能向右/下， 所以只有一条路径
                    dp[j] = 1;
                } else {
                    dp[j] = dp[j] + dp[j - 1];
                }
            }
        }
        return dp[n - 1];
    }
}

space: O(m * n)
class Solution {
    public int uniquePaths(int m, int n) {
        // use DP 
        // DP[i][j]: the possible ways to reach grid[i][j]
        // i + 1, j + 1

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

zhangyalei1026 commented 3 years ago

思路

状态方程， dp[i][j]代表的是走到(i, j)这个点的时候所有的unique path。由于只能向下和向右走，所以到达（i，j)只能从（i- 1，j)或者是（i， j - 1)两个位置来，而到达这两个位置的unique path分别是dp[i -1][j] 以及dp[i][j - 1]，因此最后的状态方程为dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 初始化的时候要注意，因为第一行只能从左边的点来，故unique path 只有一种，所以dp[0][j] = 1，同理第一列也是一样的

代码

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        #state dp[i][j]代表从（0，0）到（i， j）点的所有unique 的path
        # dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        dp = [[0] * n for _ in range(m)]
        # initialize
        for left in range(m):
            dp[left][0] = 1
        for up in range(n):
            dp[0][up] = 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(mn) 空间复杂度分析：O(mn)

joeytor commented 3 years ago

思路

dp[i][j] 到达格子 i,j 的不同路径的数目

base case dp[i][0] = 1, dp[0][j] = 1 for all i,j 最左边的一条边和最上面的一条边不同路径的数目是 1, 因为只能向右和下走, 所以这两条路径上的节点只有一种方法能到达

动态转移 dp[i][j] = dp[i-1][j] + dp[i][j-1] 因为可以从左边或者上面到达 (i, j) 所以就是能到达 (i-1, j) 和 (i, j-1) 的路径数目之和

return dp[-1][-1] 能到达 (m,n) 的路径数目之和[-1]

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

        for i in range(m):
            dp[i][0] = 1
        for i in range(n):
            dp[0][i] = 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]

复杂度

时间复杂度: O(mn) 两重循环的时间复杂度

空间复杂度: O(mn) dp 数组的空间复杂度 (可以优化到 O(n))

pan-qin commented 3 years ago

Idea:

dp. construct a dp array[][], store the number of ways to reach position (i,j). To reach (i,j), we can either from (i-1,j), or from (i,j-1). So dp[i][j]=dp[i-1][j]+dp[i][j-1]. Base case is i=0 or j=0, those are 1.

Complexity:

Time: O(mn). Space: O(mn)

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

    }
}

leo173701 commented 3 years ago

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m==1 or n==1:
            return 1
        dp = [[0 ]*(m)]*(n)
        dp[0] = [1]*(m)

        for i in range(n):
            dp[i][0]=1       
        for i in range(1,n):
            for j in range(1,m):
                dp[i][j] = dp[i][j-1]+dp[i-1][j]
        return dp[n-1][m-1]

wangzehan123 commented 3 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];
    }
}

Laurence-try commented 3 years ago

思路

dp 2D array

代码

使用语言：Python3

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

laofuWF commented 3 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]

chang-you commented 3 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];
    }
}

ai2095 commented 3 years ago

62. Unique Paths

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

Topics

DP

思路

2D DP matrix dp[i][j] is the total # of common paths till [i][j]

代码 Python

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

复杂度分析

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

zhangzz2015 commented 3 years ago

思路

建立dp 函数，dp(x, y) 为到[x, y] 位置有多少条路径，因为只能[x-1, y] 或者[x, y-1] 到达[x, y]，因此dp(x,y) = dp(x-1, y) + dp(x, y-1) ，考虑base case。dp[0, 0] = 1。 dp[-1, i]= 0 dp[i, -1] =0。可从base case推到dp[n, m]。时间复杂度为O(nm)，空间复杂度为O(nm)。
方法2，因为dp函数只和上面，和左边有关。可压缩。时间复杂度为O(nm)，空间复杂度度O(n)。 -方法3，也可采用记忆化递归方法，dfs。时间复杂度为O(nm)，空间复杂度为O(n*m)。

关键点

代码

语言支持：C++

C++ Code:


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

        ///  
        /// define dp[i][j]  path number from [0 0] to [i][j]
        //   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][j+1] + dp[i+1][j]; 
            }
        }

        return dp[m][n]; 

    }
};

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

        ///  
        /// define dp[i][j]  path number from [0 0] to [i][j]
        //   dp[i][j] = dp[i-1][j] + dp[i][j-1]; 
        vector<int> dp1(n+1,0);
        vector<int> dp2(n+1,0); 
        int* prev = &dp1[0];
        int* current = &dp2[0]; 
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(i==0 && j==0)
                {
                   current[j+1] = 1;  
                }
                else                    
                   current[j+1] = prev[j+1] + current[j]; 
            }

            swap(prev, current);  
        }

        return prev[n]; 

    }
};

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

        unordered_map<string,int> memo;
        return dfs(m-1, n-1, memo);        
    }

    int dfs(int irow, int icol,  unordered_map<string,int>& memo)
    {
        if(irow<0 || icol<0)
            return 0; 
        if(irow==0 && icol ==0)
            return 1; 
        string node = to_string(irow)+"#"+to_string(icol); 
        if(memo.find(node)!=memo.end())
            return memo[node]; 

        int sum = dfs(irow-1, icol, memo) + dfs(irow, icol-1, memo); 

        memo[node] = sum;
        return sum;             
    }
};

littlemoon-zh commented 3 years ago

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

        for i in range(m-1):
            for j in range(1, n):
                line[j] += line[j-1]
        # print(line)
        return line[-1]

kidexp commented 3 years ago

thoughts

dp[i][j]表示从0，0到i，j有多少个unique path

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

可以用滚动数组优化到O(n)

code

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

Complexity

时间复杂度O(mn)

空间复杂度O(mn)

falconruo commented 3 years ago

思路:

方法一、二维数组记录状态， dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

复杂度分析: 方法一

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

代码(C++):

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;
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

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

WangyingxuHalo commented 3 years ago

思路：方法一、二维数组记录状态， dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

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

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

carterrr commented 3 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 = 1; 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][j-1] + dp[i - 1][j];
            }
        }
        return dp[m - 1][n - 1];
    }
}

tongxw commented 3 years ago

思路

dp(m,n): 到达第m行n列的不同路径总数 dp(i,0) = dp(0, j) = 1 转移方程 dp(i,j) = dp(i-1, j) + dp(i, j-1) 爬楼梯的2D版本

代码

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

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

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

yan0327 commented 3 years ago

思路：又是学习dp思路的一天：机器人=》向下或者向右说明dp[i][0]和dp[0][j]均为1，说明状态只可能来源于dp[i-1][j]和 dp[i][j-1]的路径数目之和所以可列动态方程： dp[i][j] = dp[i-1][j]和 dp[i][j-1] 最后输出最终答案。

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

BpointA commented 3 years ago

思路

用数学做的，本质是往右需要走m-1步，往下需要走n-1步，于是问题就变成在m+n-2里面选m-1个位置。可以用for写，但是会有精度问题，需要round，直接用math库的comb更方便。

Python3代码

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        r=m-1
        d=n-1
        total=r+d
        ans=1
        for i in range (total,total-r,-1):
            ans*=i

        for i in range(1,r+1):
            ans/=i
        return round (ans)

或

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        import math
        r=m-1
        d=n-1
        total=r+d
        return math.comb(total,r)

复杂度

时间：O(m+n)

空间：O(1)

ZacheryCao commented 3 years ago

Idea:

DP. dp[i][j] = dp[i-1][j] + dp[i][j-1]. dp[i][j] how many paths to get (i, j). Because it can only go down or right, so the paths to point (i,j) is the summation of paths to point (i-1,j) and point (i,j-1)

Code:

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

Complexity:

Time: O(m * n)

Space: O(m * n)

CoreJa commented 3 years ago

思路

把棋盘看成动规状态，每个格子表示从这个格子到终点的路径数。

显然在终点的正上方和正左方的格子都只有一条路，所以初始化为1。在每个格子上只有向下或想右两条路，所以其他的格子路径数可由正下方和正右方的路径数相加得到。即

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

代码

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)

Francis-xsc commented 3 years ago

思路

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

代码


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.back().back();
    }
};

复杂度分析

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

ychen8777 commented 3 years ago

思路

DP, mem[i][j] = mem[i-1][j] + mem[i][j-1];

代码

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

        int[][] mem = new int[m][n];

        // fill first row and first column
        for (int i = 0; i < m; i++) {
            mem[i][0] = 1;
        }

        for (int j = 1; j < n; j++) {
            mem[0][j] = 1;
        }

        // fill rest
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                mem[i][j] = mem[i-1][j] + mem[i][j-1];
            }
        }

        return mem[m-1][n-1];

    }
}

复杂度

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

yingliucreates commented 3 years ago

link:

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

代码 Javascript

const uniquePaths = function (m, n) {
  const res = [];
  for (let i = 0; i < n; i++) res.push([...new Array(m).fill(1)]); // initialize list
  for (let i = 1; i < n; i++) {
    for (let j = 1; j < m; j++) {
      res[i][j] = res[i - 1][j] + res[i][j - 1];
    }
  }
  return res[n - 1][m - 1];
};

ZJP1483469269 commented 3 years ago

题目地址(62. 不同路径)

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

题目描述

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

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

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

 

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

输入：m = 3, n = 3
输出：6

 

提示：

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

前置知识

公司

暂无

思路

关键点

代码

语言支持：Java

Java Code:


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

复杂度分析

令 n 为数组长度。

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

septasset commented 3 years ago

代码(Python)

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

jaysonss commented 3 years ago

思路

状态转移方程： 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+1][n+1];
        dp[1][1] = 1;

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

时间和空间复杂度都是O(m*n)

bingyingchu commented 3 years ago


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]
Time/Space: O(M ∗ N)

ChenJingjing85 commented 3 years ago

思路

dp：状态转移方程： dp[i][j] = dp[i-1][j] + dp[i][j-1] 注意初始化为1，注意行列

代码


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1 for _ in range(n)] for _ in range(m)] #从0,0走到x，y的路径数
        for x in range(1,m):
            for y in range (1,n):
                dp[x][y] = dp[x-1][y] + dp[x][y-1]
        return dp[-1][-1]
### 复杂度分析
* 时间复杂度 O(m*n)
* 空间复杂度 O(m*n)

chenming-cao commented 3 years ago

解题思路

动态规划。题目规定机器人只能向下或向右移动，所以到达最上面一行的任意一个格子只有1种路径（向右走），到达最左边一列的任意一个格子只有1种路径（向下走）。状态转移方程：对于其他格子，可以从该格子的上方格子向下走或左边格子向右走到达，路径数等于上方格子路径数和左边格子路径数之和, path[i][j] = path[i - 1][j] + path[i][j - 1]。最后返回右下角格子的结果path[m - 1][n - 1]即可。

代码

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] path = new int[m][n];
        // Base cases:
        // top row, can only move left, there is only one way to get to the point
        Arrays.fill(path[0], 1);
        // left column, can only move down, there is only one way to get to the point
        for (int i = 0; i < m; i++) {
            path[i][0] = 1;
        }
        // calculate the path for other points
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // number of paths for the point = number of paths for the point above it
                // + number of paths for the point to the left of it
                path[i][j] = path[i - 1][j] + path[i][j - 1];
            }
        }
        return path[m - 1][n - 1];
    }
}

复杂度分析

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

watermelonDrip commented 3 years ago

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

ForLittleBeauty commented 3 years ago

思路

从右下角的简单情况开始想，然后推理上一个格子能走的路径数目和已经走了的格子的关系，然后自底向上动归。最后优化一下空间复杂度，用一行计算就可以。

代码

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

时间复杂度: O(mn)

空间复杂度: O(n)

15691894985 commented 3 years ago

题目地址(62. 不同路径)

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

思路：二维DP 状态转移方程就是由只能向下移动和向右移动 dp[i] [j]代表ij位置存在的到达路径

    class Solution:
        def uniquePaths(self, m: int, n: int) -> int:
            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]

复杂度分析：

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

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

thinkfurther commented 3 years ago

思路

从左边和上边的状态和

代码

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

复杂度

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

空间复杂度：O(N)

yuxiangdev commented 3 years ago

逐行累加各列的总可能路径数，把二维dp数组降到一维

public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) return 1;
        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 - 1];
            }
        }
        return dp[n - 1];
    }

Time: O(mn) Space: O(n)

ghost commented 3 years ago

题目

Unique Paths

思路

DP

代码


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

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

        return dp[-1]

## **复杂度**

Space: O(n)
Time: O(m*n)

yibenxiao commented 3 years ago

【Day 58】62. 不同路径

思路

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

代码

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

复杂度

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

空间复杂度：O(N)

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

【Day 58 】2021-11-06 - 62. 不同路径 #77

62. 不同路径

入选理由

题目地址

前置知识

题目描述

思路:

dp数组

已AC的C++代码:

复杂度分析

思路

关键点

代码

思路

代码

复杂度分析

Idea

Python

JavaScript

time O(m * n) space O(n)

思路

代码

复杂度

思路

代码(C++)

复杂度分析

代码

思路

代码

复杂度分析

思路

复杂度

Idea:

Complexity:

思路

代码

62. Unique Paths

Topics

思路

代码 Python

复杂度分析

思路

关键点

代码

thoughts

code

Complexity

思路

代码

思路

Python3代码

复杂度

Idea:

Code:

Complexity:

思路

代码

复杂度

思路

代码

思路

代码

复杂度

link:

代码 Javascript

题目地址(62. 不同路径)

题目描述

前置知识

公司

思路

关键点

代码

代码(Python)

思路

思路

代码

解题思路

代码

思路