Question

http://www.lintcode.com/en/problem/unique-paths/
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.

How many possible unique paths are there?

Example

Given m = 3 and n = 3, return 6.
Given m = 4 and n = 5, return 35.
Given m = 6 end = 63, return 9657648

Answer

// brute force solution, Time Limit Exceeded
// help us get dp formula pattern
// res[i][j] = res[i-1][j] + res[i][j-1];
public int uniquePaths(int m, int n) {
    return helper(1, 1, m, n);
}
private int helper(int row, int col, int m, int n)
{
    if(row == m && col == n)
        return 1;  
    if( row > m || col > n)
        return 0;
    return helper(row+1, col, m, n) + helper(row, col+1, m, n);
}

// dp solution
class Solution {
public:
    /*
     * @param m: positive integer (1 <= m <= 100)
     * @param n: positive integer (1 <= n <= 100)
     * @return: An integer
     */
    int uniquePaths(int m, int n) {
        // write your code here
        if (m <= 0 || n <= 0)
            return 0;
        vector<int> res(n);
        res[0] = 1;
        for (int i = 0; i < m; i++) {
             for (int j = 1; j < n; j++) {
                  res[j] += res[j-1];
             }
        }
        return res[n-1];
    }
};