62. Unique Paths Leetcode Java

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.

Solution:

Dynamic programming

Clearly, for the top row, res[0][j]=res[0][j-1], because there is only one possible path which is from left to right. Similarly for the left column, res[i][0]=res[i-1][0]. All other points in the grid hold res[i][j]=res[i-1][j]+ res[i][j-1].

According to this recursion analysis, we can calculate the unique paths to any point in the grid. 

As we only need to find the the unique paths to the "Finish" point, we can use one dimension array to iterativly update the information. Eg. res[i][j]=res[i-1][j]+ res[i][j-1] => res[j](current loop with i)=res[j](last loop with i-1)+res[j-1],.

Time complexity O(m*n) Extra space: O(n)

 public int uniquePaths(int m, int n) {  
    int[] res=new int[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];  
   }