网友的做法:只能向右走或者向下走,所以从一共需要的步数中挑出n-1个向下走,剩下的m-1个就是向右走
使用排列组合的方法很快的呀。
我的做法就没那么好了呀:
import java.util.*;
public class Solution {
/**
*
* @param m int整型
* @param n int整型
* @return int整型
*/
public int uniquePaths (int m, int n) {
// write code here
int[][] myInt = new int[m][n];
for(int i = 0; i< m; i++){
myInt[i][n-1] = 1;
}
for(int i = 0; i<n; i++){
myInt[m-1][i] = 1;
}
if(m>= 2 && n>= 2){
for(int i = n - 2; i>= 0; i--){
for(int j = m - 2; j>= 0; j--){
myInt[j][i] = myInt[j+1][i] + myInt[j][i+1];
}
}
}
return myInt[0][0];
}
private int myRoadNum(int m,int n){
if(m == 1 && n == 1){
return 1;
}
int n1 = 0,n2 = 0;
if(m>1){
n1 = uniquePaths(m-1,n);
}
if(n > 1){
n2 = uniquePaths(m,n-1);
}
return n1+n2;
}
}

京公网安备 11010502036488号