62. 不同路径

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

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

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

例如，上图是一个7 x 3 的网格。有多少可能的路径？

示例 1:

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

示例 2:

输入: m = 7, n = 3
输出: 28

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9

思路一：最常规的动态规划

动态规划，利用了一个m*n大小的矩阵

动态规划转态转移方程， dp[i][j] = d[i][j-1] + dp[i-1][j];

 1 class Solution {
 2     public int uniquePaths(int m, int n) {
 3         // 动态规划
 4         int[][] dp = new int[m][n];
 5         for(int i = 0; i < m; i++){     // 第一列都为1
 6             dp[i][0] = 1;
 7         }
 8         for(int j = 0; j < n; j++){     // 第一行都为1
 9             dp[0][j] = 1;
10         }
11         for(int i = 1; i < m; i++){
12             for(int j = 1; j < n; j++){
13                 dp[i][j] = dp[i-1][j] + dp[i][j-1];
14             }
15         }
16         return dp[m-1][n-1];
17     }
18 }

leetcode 执行用时：0 ms > 100.00%, 内存消耗：35.9 MB > 5.11%

复杂度分析：

时间复杂度：需要遍历整个dp数组，所以是O(m*n)

空间复杂度：需要一个O(m*n)的矩阵，所以空间复杂度O(m*n)

思路二：利用了一个(m+1)*(n+1)大小的矩阵来简化初始化步骤

动态规划转态转移方程， dp[i][j] = d[i][j-1] + dp[i-1][j];

 1 class Solution {
 2     public int uniquePaths(int m, int n) {
 3         // 动态规划
 4         int[][] dp = new int[m+1][n+1];
 5         dp[0][0] = 1;
 6         dp[0][1] = 1;
 7         for(int i = 1; i <= m; i++){
 8             for(int j = 1; j <= n; j++){
 9                 dp[i][j] = dp[i-1][j] + dp[i][j-1];
10             }
11         }
12         return dp[m][n];
13     }
14 }

leetcode 执行用时：0 ms > 100.00%, 内存消耗：35.9 MB > 6.81%

复杂度分析：

时间复杂度：需要遍历整个dp数组，所以是O(m*n)

空间复杂度：需要一个O((m+1)*(n+1))的矩阵，所以空间复杂度O((m+1)*(n+1))

思路三：利用一维矩阵实现动态规划

其实每行的dp[i][j]都只和上一行的dp[i-1][j]和左边的那个dp[i][j-1]两个元素有关，所以我们采用一维矩阵，矩阵大小为列的大小，即n , 每次求出一行的dp[j], 仔细想想，其实变成一维矩阵后，dp[j] = dp[j-1] + dp[j];

而dp[j-1]刚好在dp[j]之前就更新过了，而dp[j]在这个等式赋值之前也刚好是上一层的dp[i-1][j], 所以完美的使用一维矩阵降低了空间复杂度

 1 class Solution {
 2     public int uniquePaths(int m, int n) {
 3         // 动态规划
 4         int[] dp = new int[n];
 5         for(int j = 0; j < n; j++){     // 第一行都为1
 6             dp[j] = 1;
 7         }
 8         for(int i = 1; i < m; i++){
 9             for(int j = 0; j < n; j++){
10                 if(j == 0){
11                     dp[j] = 1;
12                 }else{
13                     dp[j] = dp[j-1] + dp[j];
14                 }
15             }
16         }
17         return dp[n-1];
18     }
19 }

leetcode 执行用时：0 ms > 100.00%, 内存消耗：35.3 MB > 96.51%, 可以看出，空间效率提高了很多

复杂度分析：

时间复杂度：需要把dp[]遍历 m遍， 所以时间复杂度为O(n*m)

空间复杂度：需要一个O(n)的矩阵，所以空间复杂度On)