算法力扣刷题记录七十四【62.不同路径】

前言

动态规划第5篇。

记录七十四【62.不同路径】

一、题目阅读

一个机器人位于一个 m x n 网格的左上角，m行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 * 10^9

二、尝试实现

分析题目，确定方法

题目说机器人只能向下或者向右走，类似跳格子的游戏。
问到达某个格子有几种路径，可以从其左边的格子向右跨一步到位；可以从其上面的格子向下跨一步到位。是一种状态转变。
所以应该用动态规划。

动规五步

确定dp数组含义和下标含义。这是一个网格，有行有列，所以需要二维数组。dp[i][j]含义：到达第i+1行第j+1列的格子有dp[i][j]条路径。

这里有个错位：i =0——第一行；i=1——第二行；i=2——第三行……；列同理。

递推公式：dp[i][j] = dp[i-1][j] + dp[i][j-1]。原因：从其左边的格子向右跨一步到位；可以从其上面的格子向下跨一步到位。
初始化：回到含义上，数值代表有几条路径，注意不是到这个格子要走几步。所以第一行初始化全为1；第一列初始化全为1。因为只能向下或者向右，向上或向左不允许。
遍历顺序：

从递推公式上看，行应该从上到下，因为用到dp[i-1]；列应该从左到右，因为用到dp[j-1]。
那么谁在外面，谁在里面？其实都可以。可以先行再列，也可以先列再行。

出错时：dp数组打印debug。

代码实现

注意点：有个用例是m=1,n=1。本来以为不应该动，所以路径是0条；但是结果给的是1，稍微改动dp[0][0] =1即可。

class Solution {
public:int uniquePaths(int m, int n) {//定义dp数组vector<vector<int>> dp(m,vector<int> (n,0));dp[0][0] = 1;//初始化第一行和第一列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][j-1]+dp[i-1][j];}}return dp[m-1][n-1];}
};

三、参考学习

记录七十四【62.不同路径】参考学习链接

学习内容

动规重点是状态转移公式，如果发现状态可以有前面的推导出来，那么应该用动态规划。可是动态规划也有for循环，重复执行同一段代码，递归也是重复执行同段代码。那么题目用递归也可以。这是图论里的深度搜索，代码如下：

class Solution {
private:int dfs(int i, int j, int m, int n) {if (i > m || j > n) return 0; // 越界了if (i == m && j == n) return 1; // 找到一种方法，相当于找到了叶子节点return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);}
public:int uniquePaths(int m, int n) {return dfs(1, 1, m, n);}
};

可是递归在可以用动态规划的题目中，很容易无法通过，因为超时错误。分析时间复杂度：分析方法在记录七十中提到。递归深度：对于行递归是m行，对于列递归是n列。深度是m+n-1。树的节点有2^(m+n-1)-1，指数级别O(2ⁿ)的时间复杂度。
动态规划的分析同二、思路。优化成一维数组：一维数组相当于边遍历边替换，替换成新的一行。

递推公式：dp[i]下标i是列的含义，更新之前的dp[i]等同于dp[i-1][j]，加上dp[i-1]等同于dp[i][j-1]后，新的dp[i] = dp[i] (原有)+dp[i-1]。因为列从左往右，所以dp[i-1]已经更新。
代码实现：

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

数论：思路——走到终点，一定要向下走m-1步，向右走n-1步。总共走m+n-2步，其中m-1步向下，什么时候走都可以，所以求公式：C^m-1_m+n-2.
防止溢出。边计算边化简。

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