Description:
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?
Solution:
Time Complexity : O(n^2)
Space Complexity: O(n)
var uniquePaths = function(m, n) {
// Create dp array
const dp = new Array(n + 1).fill(1);
// Populate dp array
for(let row = m - 1; row > 0; row--){
for(let col = n - 1; col > 0; col--){
dp[col] = dp[col] + dp[col + 1];
}
}
return dp[1];
}
Top comments (1)
I found that solution very popular and helpful: https://www.youtube.com/watch?v=Z-uMFv_-w2s&ab_channel=EricProgramming