Unique Paths

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 7 x 3 grid. How many possible unique paths are there?
Note: _m _and _n _will be at most 100.
Example 1:
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right
Example 2:
Input:
m = 7, n = 3
Output:
28

Analysis

标准的二维动态规划问题
状态dp[i][j] - 从起点到达(i, j)的路径数目 状态转移方程: dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; - 左侧(i, j - 1)和上方 (i - 1, j)位置的路径之和,因为从左侧和上方到达(i, j)均只有一种路径 初始条件: dp[i][0] = 1 (i = 0, ... m - 1), dp[0][j] = 1 (j = 0, ..., n - 1)
答案dp[m - 1][n - 1] 即终点位置
同时另一种思路是转化为排列组合问题,即:需要走 m + n - 2 步,其中 m - 1向下,n - 1向右。也就是求解组合数:
C(m + n - 2, n - 1)

Solution

2D DP - O(mn) space, O(mn) time - (0ms, 100% AC)
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
// initialization
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n; j++) {
dp[0][j] = 1;
}
// state transfer function
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
class Solution {
public:
int uniquePaths(int m, int n) {
int N = n + m - 2;// how much steps we need to do
int k = m - 1; // number of steps that need to go down
double res = 1;
// here we calculate the total possible path number
// Combination(N, k) = n! / (k!(n - k)!)
// reduce the numerator and denominator and get
// C = ( (n - k + 1) * (n - k + 2) * ... * n ) / k!
for (int i = 1; i <= k; i++)
res = res * (N - k + i) / i;
return (int)res;
}
};

Reference