1.题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
2.解题思路
动态规划
（1）初始化
1) 从[0,0]走到[0,0]的路径，即没走，设dp[0][0] = 0; 2) 如果m*n的n为1，即机器人在m*1走，只能有一条路径，即arr[i][0] = 1; 3) 如果m*n的m为1，即机器人在1*n走，只能有一条路径，即arr[0][1] = 1;(2) 动态规划核心算法
机器人每次只能向下或者向右移动一步。即机器人arr[i][j]的路径由arr[i-1][j]和arr[i][j-1]决定，即arr[i][j] = arr[i-1][j]+arr[i][j-1];
3.代码
class Solution {
public static int uniquePaths(int m, int n) {
if(m < 0 || n < 0)
return 0;
int arr[][] = new int[m][n];
//初始化
arr[0][0] = 0;
//初始化列
for(int i = 0;i<n;i++){
arr[0][i] = 1;
}
//初始化行
for(int i = 0;i<m;i++){
arr[i][0] = 1;
}
//动态规划
for(int i =1;i<m;i++){
for(int j = 1;j<n;j++){
arr[i][j] = arr[i-1][j]+arr[i][j-1];
}
}
return arr[m-1][n-1];
}
}