leetcode刷题（122）——62. 不同路径
一个机器人位于一个 m x 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 * 109
动态规划
对于(0,0)这个点来说，它只能往右走、或者往下走。 那么反过来看，哪个点可以到达(2,2)呢？
只能是它的上方(1,2)这个点 或者是它的左方(2,1)这个点
搞清楚这个关系，动态规划的转移方程就可以很容易写出来了：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]解决了核心逻辑，再把边界条件处理下就可以了。 递归的边界条件是走到了最右边一列、或者是走到了最下面一行。 动态规划正好是反过来的，因为我们是从上到下一行一行推导的。 所以我们要处理下第一行和第一列，将它们都赋予1即可。
时间复杂度：O(M * N)O(M∗N) 空间复杂度：O(M * N)O(M∗N)
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
//第一行都赋予 1
for(int i = 0; i < m; ++i) {
dp[i][0] = 1;
}
//第一列都赋予 1
for(int j = 0; j < n; ++j) {
dp[0][j] = 1;
}
//两个for循环推导，对于(i,j)来说，只能由上方或者左方转移过来
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];
}
}动态规划+空间优化
我们在二维数组推导的时发现，dp[i][j]的值来自于dp[i - 1][j]和dp[i][j - 1]。 也就是只需要上一行的值就可以了，上上一行的并不需要了，所以这里可以用滚动数组的方式优化一下空间。
以上图所述，对于第三行10这个值，需要上方的值+左方的值。而经过上一次计算之后，第四列的值是4。 此时我们并不需要再跟上一行的做累加，只需要用4加上左边的6就可以了。 所以我们可以申请一维数组，数组长度就是n。 将原先 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 改为： dp[j] = dp[j] + dp[j - 1]。
时间复杂度：O(M * N)O(M∗N) 空间复杂度：O(N)O(N)
class Solution {
public int uniquePaths(int m, int n) {
//一维空间，其大小为 n
int[] dp = new int[n];
Arrays.fill(dp, 1);
for(int i = 1; i < m; ++i) {
for(int j = 1; j < n; ++j) {
//等式右边的 dp[j]是上一次计算后的，加上左边的dp[j-1]即为当前结果
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[n - 1];
}
}对于空间优化的补充：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 虽然用到了二维数组，但是计算第 i 行时，只需要 i - 1 行的内容就可以了 所以用一维数组来代替
那么这句就很关键:
dp[j] = dp[j] + dp[j - 1]对比下 一维和二维的这两个公式，其实有相似的地方 拿等号右边来对比说：
dp[i - 1][j] + dp[i][j - 1]
dp[j] + dp[j - 1]dp[j - 1] 就类似于 dp[i][j - 1] ，这是本行左边的那个值 dp[j] 就类似于 dp[i - 1][j] ，这里的dp[j]不是本行的，是“上一次”计算的结果 这里的重点就是“上一行”计算结果，等号右边两个值相加后又赋给了dp[j] 那么下一轮再计算时， dp[j]的值就是“上一次”计算的结果了
# dp[i - 1][j] 是来自上方的，dp[i][j - 1]来自左边
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
# dp[j] 是上一次迭代计算后的当前位置，相当于二维数组中的“上方”
# dp[j - 1] 是刚刚计算后的左边，相当于二维数组中的“左边”
dp[j] = dp[j] + dp[j - 1];二维和一维都是从左往右更新的，所以计算dp[j]时，dp[j - 1]就已经计算好了 于是拿着 上一次迭代后的当前位置 + 刚刚计算后的左边位置，加起来就是当前结果了 而这个结果会被继续使用到 可以看下题解里面的最后一张图，那个就是一行一行更新后的效果
下面的图，就是叠加后的示例结果：
腾讯云开发者
