A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.A:
另外,其实,可以免掉recursive调用,直接在数组上来计算的。
----第二遍 Iterative way, using 2D array----
public class Solution { public int uniquePaths(int m, int n) { if(m<=1||n<=1) return 1; int[][] A = new int[m][n]; Arrays.fill(A[0],1); for(int i =1;i<m;i++) for(int j =0;j<n;j++) A[i][j] = j==0?1:A[i-1][j]+A[i][j-1]; return A[m-1][n-1]; } }
利用一维数组 using 1D array
public class Solution { public int uniquePaths(int m, int n) { int[] A = new int[n]; Arrays.fill(A,1); for(int i =1;i<m;i++) for(int j =1;j<n;j++) A[j] += A[j-1]; return A[n-1]; } }
第一个是recursively 调用,同时用一个数组,来记录已经用过的调用。
public class UniquePaths { public int uniquePaths(int m, int n) { // DP int[][] pathNum = new int[m + 1][n + 1];// ignore the 0 row and col return recursivePath(pathNum, m, n); } private int recursivePath(int[][] pathNum, int row, int col) { if (pathNum[row][col] != 0) { return pathNum[row][col]; } else { // else ,we need calculate them if (row == 1 && col == 1) { pathNum[1][1] = 1; return 1; } // now we can reduce their case int stepDown = 0; if (row >= 2) { stepDown = recursivePath(pathNum, row - 1, col); pathNum[row - 1][col] = stepDown; } int stepRight = 0; if (col >= 2) { stepRight = recursivePath(pathNum, row, col - 1); pathNum[row][col - 1] = stepRight; } return stepRight + stepDown; } } }
No comments:
Post a Comment