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];}
}