leetcode hot100不同路径

本题可以采用动态规划来解决。还是按照五部曲来做
确定dp数组：dp[i][j]表示走到（i，j）有多少种路径

确定递推公式：我们这里，只有两个移动方向，比如说我移动到（i，j）那么只能从（i-1，j）或者从（i，j-1）移动，所以，dp[i][j] = dp[i-1][j] + dp[i][j-1]。因为我们求的是路径，并不是步数，所以从dp[i-1][j]到dp[i][j]只有一个路径，同理，所以二者相加即可。

初始化：我们要知道，只能向下或者向右走，也就是说只有两个移动方向，那么如果我们只在第一行移动的时候，dp[0][j]=1，数组的值都是1；同理，只在第一列上移动，dp[i][0]=1；

遍历顺序：我们直接从左到右从上到下依次遍历即可（题中规定）

打印

class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];for(int i = 0;i<m;i++){dp[i][0] = 1;}for(int j = 0;j<n;j++){dp[0][j] = 1;}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];}
}

注意：

1. 初始化的时候，按照上述分析直接初始化即可，第一行或者第一列只有一种路径。
2. 在初始化的时候，只需要初始化到m-1/n-1，因为我们是从下标0开始的。
3. 在遍历的时候，我们应该从1开始，因为0已经初始化了（行/列）。我们for循环结束的条件就是i<m/j<n，因为我们最后是要走到（i，j）的路径个数，但数组我们是从0开始的，所以只需要<m就可以，并不需要i<=m，并直接返回dp[m-1][n-1]即可。