LeetCode—— 62 不同路径

问题描述：

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

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

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/unique-paths 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

执行结果：

代码描述：

思路：

先处理第一行，i = 0，当做目标就在第一行，此时，只能向右走，所以只有1种方案。表现在图中就是第一行都为1.

处理第二行第一个，此时j=0，当做目标就在第一列，所以，只能下走，也就只有1种方案。表现在图中就是第一列都为1.

继续处理，当目标在(1,1),索引从0开始，此时有2种方案。当目标在(1,2), 此时有上一位置的方案数，加上即将要走的方案数，

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

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

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

继续，将空间复杂度调小，改为如下：时间复杂度O(n*m)， 空间复杂度O(n).

计算过程如下：黑色为第一行的初始值，红色为第二行的计算结果，绿色为第三行的计算结果，蓝色为第四行的计算结果，最后的结果为最后一个数。

1/1/1/11/2/3/41/3/6/101/4/10/201/5/15/35 class Solution { public: int uniquePaths(int m, int n) { vector<int> dp(n,1); // 初始化第一行为1 for(int i = 1; i < m; ++i) { for(int j = 1; j < n; ++j) { dp[j] += dp[j-1]; } } return dp[n-1]; } };

动态规划最常规的路径问题，参考：最短路径