# Leetcode 62 Unique Paths.

Problem 62 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 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

I think most people would think this as a backtracking problem.

The code can be really simple, too.

``````public class Solution {
public int uniquePaths(int m, int n) {
if(m==1 || n==1){
return 1;
}
return uniquePaths(m-1,n)+uniquePaths(m,n-1);
}
}``````

But, it will show Time Limit Exceeded.

So DP should be a good way to solve this.

``````public class Solution {
public int uniquePaths(int m, int n) {
if(m==1||n==1){
return 1;
}
int[][] pathnum=new int[m][n];
for(int i=1;i< m;i++){
pathnum[i][0]=1;
}
for(int j=1;j< n;j++){
pathnum[0][j]=1;
}
for (int i=1;i< m;i++){
for(int j=1;j< n;j++){
pathnum[i][j]=pathnum[i-1][j]+pathnum[i][j-1];
}
}
return pathnum[m-1][n-1];
}
}``````