描述 :
一个机器人位于一个?m x n
?网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
题目 :
LeetCode 62.不同路径 :
解析 :
第一种方式 : (递归 , 但是这种会超时间限制)
class Solution {
public int uniquePaths(int m, int n) {
return dp(m,n);
}
public int dp(int m,int n){
if(n == 1 || m == 1){
return 1;
}
return dp(m - 1,n) + dp(m,n - 1);
}
}
第二种方式 : (二维数组)
class Solution {
public int uniquePaths(int m, int n) {
int[][] arr = new int[m][n];
arr[0][0] = 1;
for(int i = 0;i < m;i++){
for(int j = 0;j < n;j++){
if(i > 0 && j > 0){
arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
}else if(i > 0){
arr[i][j] = arr[i - 1][j];
}else if(j > 0){
arr[i][j] = arr[i][j - 1];
}
}
}
return arr[m - 1][n - 1];
}
}
这期就到这里 , 下期见!