网友的做法:只能向右走或者向下走,所以从一共需要的步数中挑出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; } }