【Day 58 】2022-12-28 - 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

[Ryanbaiyansong]

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

        for i in range(n):
            f[0][i] = 1

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

        return f[-1][-1]

[zjsuper]

class Solution: def uniquePaths(self, m: int, n: int) -> int:

dp

    ans = [[0 for _ in range(n)] for _ in range(m)]
    ans[0][0] = 1
    for i in range(m):
        for j in range(n):
            if i == 0 and j ==0:
                continue
            elif i == 0 and j != 0:
                ans[i][j] = 1
            elif i != 0 and j == 0:
                ans[i][j] = 1
            else:
                ans[i][j] = ans[i-1][j] + ans[i][j-1]
    return ans[-1][-1]

[zywang0]

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

[heng518]

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

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

    for(int j = 0; j < m; j++)
        dp[j][n] = 0;

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

        }
    }
    return dp[0][0];
}

};

[Abby-xu]

思路

DFS

代码

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)

复杂度

...

[ringo1597]

代码

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

[mayloveless]

思路

状态转移方程：(i,j)这个位置只有可能通过(i-1,j)和(i,j-1)两个位置过来。边界的地方可以通过一个位置过来

代码

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

复杂度

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

[bookyue]

code

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

        return dp[n - 1];
    }

[chenming-cao]

解题思路

动态规划。题目规定机器人只能向下或向右移动，所以到达最上面一行的任意一个格子只有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)

[Elsa-zhang]

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

[yuxiangdev]

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

}

[testplm]

var uniquePaths = function(m, n) {
    // m-1个右，n-1个下
    // 相当于有m个空，让n-1个下排雷组合
    // C  n-1+m-1
    // Total permutations = (m+n)! / (m! * n!)
    if(m === 1 || n === 1) return 1;
    m--; n--;
    // Swap, so that m is the bigger number
    if(m<n){
        m=m+n;
        n=m-n;
        m=m-n;
    }
    let res=1;
    let j=1;
    for(let i=m+1;i<=m+n;i++,j++){
        res*=i;
        res/=j;
    }
    return res;
};

[bwspsu]

(Referring to solution)

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]

[chiehw]

思路：动态规划

(i, j) 的路径数 = (i-1, j) + (i, j-1)

代码

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

[snmyj]

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

[whoam-challenge]

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

[saitoChen]

思路

dp[i][j]表示在m,n的网格中，走到i，j的位置上时有dp[i][j]条不同的路径 递推公式：dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 初始值：所有横纵坐标有0的一律为0，有1的一律为1

代码

const dp = new Array(m+1).fill(0).map(() => 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(N^2)

[Jetery]

62. 不同路径

思路

路径问题

代码 (cpp)

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

复杂度分析

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

[RestlessBreeze]

代码

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

[JancerWu]

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

[tiandao043]

思路

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

[AstrKing]

思路

dp[i][j]表示在m,n的网格中，走到i，j的位置上时有dp[i][j]条不同的路径，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

代码

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(n2)

空间复杂度：O(n)

[Elon-Lau]

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

[klspta]

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

[buer1121]

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

    # ###节省空间
    cur = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            cur[j] += cur[j-1]
    return cur[-1]

[BruceZhang-utf-8]

代码

• 语言支持：Java

Java Code:

class Solution {
    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];
    }
}

[paopaohua]

class Solution {
    public int uniquePaths(int m, int n) {
        // 定义dp
        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];

    }
}

[GG925407590]

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

[MaylingLin]

思路

---

动态规划建模

代码

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: $O(m*n)$，
• Space: $O(m*n)$

[AtaraxyAdong]

class Solution {
    public int uniquePaths(int m, int n) {
        // 优化方式
        // 第 i 行 第 j 列的可能数目
        int[] dp = new int[n];
        // 这是第 1（index= 0） 行的数目
        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];
    }
}

[Alexno1no2]

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

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]

[darwintk]

动态规划 转移方程为 f(i,j) = f(i-1,j)+f(i,j-1)

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

[FlipN9]

/**
    DP: 到当前这个点的 unique path 的数量
    因为只能往右或者下, 所以 第一行和第一列 所有的 dp = 1
    对于其它 cell, dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    TC: O(MN)   SC: O(MN)
*/
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < n; i++) dp[0][i] = 1;
        for (int i = 0; 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];  
    }
}