Sunday, January 4, 2015

Unique Paths (LeetCode Array)

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

Idea: Dynamic programming. Since the robot can only go right or down, path[i][j]=path[i+1][j]+path[i][j+1]. For the last column(the last row), the robot has no choice but go down (go right), so the path[i][n-1] = 1( path[m-1][j]=1 ). The result is path[0][0].

Time: O(n^2) Space: O(n^2)

Code:
 public class Solution {  
   public int uniquePaths(int m, int n) {  
     if(m==0||n==0)  
       return 0;  
     int[][] path=new int[m][n];  
     for(int j=n-1;j>=0;j--)  
       path[m-1][j]=1;  
     for(int i=m-1;i>=0;i--)  
       path[i][n-1]=1;  
     for(int i=m-2;i>=0;i--)  
     {  
       for(int j=n-2;j>=0;j--)  
         path[i][j]=path[i+1][j]+path[i][j+1];  
     }  
     return path[0][0];  
   }  
 }  

No comments:

Post a Comment