LeetCode: Unique Paths II Solution

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}/**2 * @param {number[][]} obstacleGrid3 * @return {number}4 */5var uniquePathsWithObstacles = function (obstacleGrid) {6  const [M, N] = [obstacleGrid.length, obstacleGrid[0].length]7  const memo = Array.from({ length: M }, _ => Array(N).fill(null))8
9  const recursion = (i, j) => {10    if (memo[i][j] !== null) {11      return memo[i][j]12    }13
14    if (obstacleGrid[i][j] === 1) {15      return 016    }17
18    if (i === M - 1 && j === N - 1) {19      return 120    }21
22    let numberOfWays = 023    if (i < M - 1) {24      numberOfWays += recursion(i + 1, j)25    }26    if (j < N - 1) {27      numberOfWays += recursion(i, j + 1)28    }29
30    return (memo[i][j] = numberOfWays)31  }32
33  return recursion(0, 0)34}```

Tags

leetcode

array

dynamic programming

recursion

Next Post

LeetCode: Find First And Last Position Of Element In Sorted Array

Apr 29, 2021

Search Posts