# Unique Paths

# 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];
}
};
```