Dynamic Programming
Medium
- Time complexity: O()
- Space complexity: O()
// Time O(m*n) | Space O(m*n)
var uniquePaths = function(m, n) {
const dp = Array.from({length: m}, () => Array(n).fill(0));
for(let i = 0; i < m; i++) {
dp[i][0] = 1;
}
for(let j = 0; j < n; j++) {
dp[0][j] = 1;
}
for(let i = 1; i < m; i++) {
for(let j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
};
var uniquePaths = function(m, n) {
const dp = new Array(m).fill(new Array(n).fill(1));
for (let i = 0; i < m; i += 1) {
for (let j = 0; j < n; j += 1) {
if (i === 0 && j === 0) continue;
else if (i === 0) dp[i][j] = dp[i][j - 1];
else if (j === 0) dp[i][j] = dp[i - 1][j];
else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
};
// write your code here
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up