Lintcode: 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?

Have you met this question in a real interview? 

Yes

Example

1,1	1,2	1,3	1,4	1,5	1,6	1,7
2,1
3,1						3,7

Above is a 3 x 7 grid. How many possible unique paths are there?

Note

m and n will be at most 100.

Tags Expand 

Dynamic Programming Array

Naive -- recursive solution
http://joycelearning.blogspot.com/2013/10/leetcode-unique-paths.html
Cannot pass the test:
Time: O(2^n) = O(1) + o(2^1) + O(2^2) + O(2^3)+......+O(2^n)
stack Space: O(n)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class Solution { public: /** * @param n, m: positive integer (1 <= n ,m <= 100) * @return an integer */ int uniquePaths(int m, int n) { // wirte your code here int res; res = helper(1, 1, m, n); } int helper(int idx, int idy, int m, int n){ if(idx > m || idy > n) return 0; if(idx == m && idy == n) return 1; int right = helper(idx + 1, idy, m, n); int down = helper(idx, idy + 1, m, n); return right + down; } };

Mathematical solution:
2^n only solve ways that robot start from one point to a triangle. The arithmetics will be complex to let those endings point to just the end point.
------------
| S  |     | E |
------------
|     | E |
---------
| E |
-----
Reference: http://blog.unieagle.net/2012/11/04/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Aunique-paths/
For an m, n array, the robot takes m + n -2 steps to destination, among which m -1 steps are walking down and n - 1 steps are walking right.
Then the problem is conversed to how many choices to get m - 1 from m + n - 2
The result is Cm+n-2m-1
p(n, m) = n! / (n - m)!    C(n, m) = p(n, m) / m! =n! / (n - m)! / m!

Time: O(n) level, each level is O(2^n)
Space: O(1)

Note: codes below can pass leetcode test, but cannot pass lincode test with input(17, 18).
It is because the both 17! and 18！ are very large integers, which are out of range of long long integers. This bug can be solved by changing int to double. Remember to plus 0.5 when transfer double into int.

class Solution {
public:
    /**
     * @param n, m: positive integer (1 <= n ,m <= 100)
     * @return an integer
     */
    long long int factor(int x, int start = 1){
        if(x == 1 || x == 0) return 1;
        long long int res = 1;
        while(x >= start){
   res *= x;
   x--;
  }  
        return res;
    }
    int uniquePaths(int m, int n) {
        int steps = m + n - 2;
        int downsteps = m - 1;
        int rightsteps = n - 1;
        int sidesteps = max(downsteps, rightsteps);
        long long int result = factor(steps, sidesteps + 1);
        result /= factor(steps - sidesteps);
        return result;
    }
};

Double version:

class Solution {
public:
    /**
     * @param n, m: positive integer (1 <= n ,m <= 100)
     * @return an integer
     */
    double factor(int x, int start = 1){
        if(x == 1 || x == 0) return 1;
        double res = 1;
        while(x >= start){
   res *= x;
   x--;
  }  
        return res;
    }
    int uniquePaths(int m, int n) {
        int steps = m + n - 2;
        int downsteps = m - 1;
        int rightsteps = n - 1;
        int sidesteps = max(downsteps, rightsteps);
        double result = factor(steps, sidesteps + 1);
        result /= factor(steps - sidesteps);
        return (int)(result + 0.5);
    }
};

DP:
DP explanation: http://yucoding.blogspot.com/2013/04/leetcode-question-116-unique-path-i.html

Equation: N[i][j] = N[i - 1][j] + N[i][j - 1]
Start: N[0][0] = 1; N[0][j] = 1; N[i][0] = 1
End: i = m, j = n

------------
| 1 | 1 | 1 |
------------
| 1 | 2 | 3 |
------------
| 1 | 3 | 6 |
------------

Time: O(mn)
Space: O(mn) -- it can be optimized to O(min(m,n)) with two arrays or just one array.

class Solution {
public:
    /**
     * @param n, m: positive integer (1 <= n ,m <= 100)
     * @return an integer
     */
    int uniquePaths(int m, int n) {
        int N[m][n];
        for(int i = 0; i < m; i++){
            N[i][0] = 1;
        }
        for(int i = 0; i < n; i++){
            N[0][i] = 1;
        }
        for(int j = 1; j < n; j++){
  for(int i = 1; i < m; i++){
                N[i][j] = N[i - 1][j] + N[i][j - 1];
         //cout<<"N["<<i<<"]["<<j<<"] = "<<N[i][j]<<" ";
            }
     //cout<<endl;
        }
        return N[m - 1][n - 1];
    }
};

Reference:
Several solutions and optimization: http://blog.csdn.net/kenden23/article/details/17303497



Lintcode Second::

DP solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

class Solution { public: /** * @param n, m: positive integer (1 <= n ,m <= 100) * @return an integer */ int uniquePaths(int m, int n) { // wirte your code here vector<vector<int> > hash(m, vector<int>(n)); for(int i = 0; i < m; i++){ hash[i][0] = 1; } for(int j = 0; j < n; j++){ hash[0][j] = 1; } for(int i = 1; i < m; i++){ for(int j = 1; j < n; j++){ hash[i][j] = hash[i - 1][j] + hash[i][j - 1]; } } return hash[m - 1][n - 1]; } };

Recursive: