1.题目描述

2.思路

dp含义：代表到当前位置的路径数
递推公式：dp[i][j]=dp[i-1][j]+dp[i][j-1]
dp数组初始化，我们要确保第一行和第一列是有值的.
dp数组的遍历顺序：我们需要从左往右遍历，从上往下遍历。并且把第一行和第一列初始化为1，dp[i][0]=1,dp[0][j]=1
//有 n 行（行索引从 0 到 n - 1）

//有 m 列（列索引从 0 到 m - 1）
所以最后一个格子是dp[n-1][m-1]

3.代码实现

class Solution {public int uniquePaths(int m, int n) {//m是列数，n是行数// dp[i][j] 表示从起点到 (i, j) 的路径数int[][] dp=new int[n][m];//确保第一行，也就是向右走的元素是有值的for(int j=0;j<m;j++){dp[0][j]=1;}//确保第一列，也就是向下走是有值的for(int i=0;i<n;i++){dp[i][0]=1;}//遍历的时候，当前的元素的值需要它头上的元素和左边的元素确定，这边不加1，是因为到达当前元素的值都只有向左那条路径和向下那条路径//我们求的是路径的和，不是格子步数for(int j=1;j<m;j++){for(int i=1;i<n;i++){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}//所以最后一个格子是dp[n-1][m-1]return dp[n-1][m-1];}
}