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