力扣62-不同路径（Java详细题解）

题目链接：62. 不同路径 - 力扣（LeetCode）

前情提要：

因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。

dp五部曲。

1.确定dp数组和i下标的含义。

2.确定递推公式。

3.dp初始化。

4.确定dp的遍历顺序。

5.如果没有ac打印dp数组利于debug。

每一个dp题目如果都用这五步分析清楚，那么这道题就能解出来了。

题目思路:

直接按照dp五部曲走。

1.确定dp数组和i下标的含义。

该题要求我们返回到达右下角一共有多少中不同的路径。

而且本题是在一个网格内，所以本题的dp数组是二维的。

那么dp[i] [j]就是指到达第i行j列的不同的路径。

2.确定递推公式。

题目明确，机器人每次只能向下或者向右移动一步。

所以我们第i行j列只能由它的上一行或者左边的一列得出。

dp[i] [j] 只能由 dp[i - 1] [j] 或 dp[i] [j - 1]得出。

那具体怎么得出呢，其实是他俩想加的和。

即本格的不同路径条数是由他上一行格的路径条数和左边一列的路径条数。

3.dp的初始化。

机器人只能从向下或者向右移动。而且dp[i] [j] 只能由 dp[i - 1] [j] 或 dp[i] [j - 1]得出。即本格只能从他的上一行格和左列格的路径得出，所以我们肯定要知道最上边一行和最左边一列的路径。

即dp[i] [0] 和 dp[0] [i]的路径数。

他们的路径其实为1。

为啥为1呢?

机器人只能向右或者向下移动，最上面一行其实就是机器人一直向右移动，其实就一条路径能这样走。最左边一列也同理。

所以do[i] [0] = 1,dp[0] [i] = 1;

4.dp遍历顺序。

其实dp的初始顺序可以有递推公式看出来。每一个台阶只能从他的上一个或者左列的得出。所以dp的遍历顺序是每一行从左往右，每一列从上到下。

5.打印dp数组。

如果没有出现差错，我们就可以不用打印，因为我是写题解，所以我就不添加核心代码以外的代码，不然代码显的有些冗余。

举个列子。

在这里插入图片描述

以上五步都做完，那么此题的代码就可以写出来了。

最终代码：

java">class Solution {public int uniquePaths(int m, int n) {//1.定义dp数组和i下标含义int [][] dp = new int [m + 1][n + 1];//2.递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1];//3.初始化for(int i = 0;i < m;i ++){dp[i][0] = 1;}for(int i = 0;i < n;i ++){dp[0][i] = 1;}//4.遍历顺序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];}}//最终位置就为dp[m - 1] [n - 1]return dp[m - 1][n - 1];}
}