力扣 62. 不同路径-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣 62. 不同路径。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目来源：https://leetcode.cn/problems/unique-paths/

力扣 62. 不同路径,开始C++吧,leetcode,算法,c++,动态规划,数论方法

C++题解1：动态规划。声明二维数组。

确定dp数组（dp table）以及下标的含义。dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
确定递推公式。想要求 dp[i][j] ，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]。dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。
dp数组的初始化。dp[0][0] = 1.
确定遍历顺序。这里要看一下递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。推导dp[i][j]的时候，要保证dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。
举例推导dp数组。

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

代码随想录写法：先初始化第一行和第一列。

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

C++题解2（来源代码随想录）：用数论的思想。m行n列的话，无论怎么走，走到终点都需要 m + n - 2 步。在这m + n - 2 步中，一定有 m - 1 步是要向下走的，不用管什么时候向下走。那么有几种走法呢？可以转化为，给你m + n - 2个不同的数，随便取m - 1个数，有几种取法。即 $力扣 62. 不同路径,开始C++吧,leetcode,算法,c++,动态规划,数论方法$

求组合的时候，要防止两个int相乘溢出！ 所以不能把算式的分子都算出来，分母都算出来再做除法。文章来源地址https://www.toymoban.com/news/detail-625392.html

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long numerator = 1; // 分子
        int denominator = m - 1; // 分母
        int count = m - 1;
        int t = m + n - 2;
        while (count--) {
            numerator *= (t--);
            while (denominator != 0 && numerator % denominator == 0) {
                numerator /= denominator;
                denominator--;
            }
        }
        return numerator;
    }
};

到了这里，关于力扣 62. 不同路径的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！