The basic idea is to update every cell in the matrix, since it equals to left and/or top neighbors sums. Either update boarder first then only update kernel, or update entire once with one more if check inside the loop (right boarder? bottom boarder? or inside). The start point should be set to be 1.
public class Solution {
public int uniquePaths(int m, int n) {
int[][] process = new int[m][n];
process[m-1][n-1] = 1;
// for(int i = 0; i < m - 1; i++){
// process[i][n - 1] = 1;
// }
// for(int j = 0; j < n - 1; j++){
// process[m - 1][j] = 1;
// }
for(int i = m - 1; i >= 0; i--){
for(int j = n - 1; j >= 0; j--){
if(i + 1 < m && j + 1 < n){
process[i][j] = process[i + 1][j] + process[i][j + 1];
continue; //save some time.
}
// int rightPath = 0;
if(i + 1 < m){
process[i][j] = process[i + 1][j];
continue; //save some time.
}
// int downPath = 0;
if(j + 1 < n){
process[i][j] = process[i][j + 1];
}
}
}
return process[0][0];
}
}
没有评论:
发表评论