前言
动态规划第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(2n)的时间复杂度。
- 动态规划的分析同二、思路。优化成一维数组:一维数组相当于边遍历边替换,替换成新的一行。
- 递推公式: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步向下,什么时候走都可以,所以求公式:Cm-1m+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;}
};
总结
(欢迎指正,转载标明出处)