Title: Unique Paths Source: leetcode.com
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? (image source: leetcode.com)
Note: m and n will be at most 100.
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
/* https://leetcode.com/problems/unique-paths/ */ class UniquePaths { public static void main(String args[]) { UniquePaths solution = new UniquePaths(); System.out.println(solution.uniquePaths(3, 7)); } public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) dp[i][j]=-1; } helper(m-1, n-1, dp); return dp[m-1][n-1]; } int helper(int i, int j, int[][] dp) { if(i<0 ||j<0) return 0; if(i==0 && j==0) { return dp[i][j]=1; } else { dp[i][j] = dp[i][j]!=-1?dp[i][j]:(helper(i-1, j, dp) + helper(i, j-1, dp)); return dp[i][j]; } } } |