Question
from lintcode
A robot is located at the top-left corner of a m x n grid.
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.
Notice
m and n will be at most 100.
Have you met this question in a real interview? Yes
Example
Given m = 3 and n = 3, return 6.
Given m = 4 and n = 5, return 35.
Idea
One path to start.
f[0][0] = 1
Number of paths to reach each 1st row (0-index) element = paths from left, cuz there're no top elements
f[0][any column] = f[0][previous column]
Number of paths to reach each 1st column (0-index) element = paths from top, cuz there're no left columns
f[any row][0] = f[previous row][0]
Number of paths to reach position x,y = paths from left + paths from top
f[row][column] = f[row][column - 1] + f[row - 1][column]
/**
*
* One path to start.
* f[0][0] = 1
*
* Number of paths to reach each 1st row (0-index) element = paths from left, cuz there're no top elements
* f[0][any column] = f[0][previous column]
*
* Number of paths to reach each 1st column (0-index) element = paths from top, cuz there're no left columns
* f[any row][0] = f[previous row][0]
*
* Number of paths to reach position x,y = paths from left + paths from top
* f[row][column] = f[row][column - 1] + f[row - 1][column]
*
* You need to remember two rows of result.
*/
public class Solution {
/**
* @param m: positive integer (1 <= m <= 100)
* @param n: positive integer (1 <= n <= 100)
* @return: An integer
*/
public int uniquePaths(int m, int n) {
int rowLen = m, colLen = n;
int[][] ways = new int[this.rowsToRemember][colLen];
// f[0][0] = 1
ways[0][0] = 1;
// f[0][any column] = f[0][prev Column], for 1st row has no upper rows
for(int column = 1; column < colLen; column++)
ways[rowIndexOf(0)][column] = ways[rowIndexOf(0)][column - 1];
// f[any row][0] = f[prev row][0], for 1st column has no left column
for(int row = 1; row < rowLen; row++)
ways[rowIndexOf(row)][0] = ways[rowIndexOf(row - 1)][0];
// f[row][column] = f[row][column - 1] + f[row - 1][column]
for(int row = 1; row < rowLen; row++)
for(int column = 1; column < colLen; column++) {
ways[rowIndexOf(row)][column] = ways[rowIndexOf(row)][column - 1] + ways[rowIndexOf(row - 1)][column];
}
return ways[rowIndexOf(rowLen - 1)][colLen - 1];
}
private int rowsToRemember = 2;
private int rowIndexOf(int i) {
return i % rowsToRemember;
}
}
网友评论