Last active
August 5, 2022 17:12
-
-
Save kishan-dhankecha/0dac8c3e9ba22971c15c3ac3b92497be to your computer and use it in GitHub Desktop.
Grid Traveler function with memoization [JAVASCRIPT]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/// Say that you are a traveler on a 2D grid. You begin in the | |
/// top-left corner and your goal is to travel to the bottom-right | |
/// corner. You may only move down or right. | |
/// In how many ways can you travel to the goal on a grid with | |
/// dimensions m * n? | |
/// Write a function 'gridTraveler(m, n)' that calculates this. | |
const gridTraveler = (n, m, memory = {}) => { | |
// LTR check in memory. | |
if (`${n},${m}` in memory) return memory[`${n},${m}`]; | |
// RTL check in memory. | |
if (`${m},${n}` in memory) return memory[`${m},${n}`]; | |
// Return obvious values to stop recursion. | |
if (n == 1 || m == 1) return 1; | |
if (n == 0 || m == 0) return 0; | |
// Store current value in memory. | |
memory[`${n},${m}`] = gridTraveler(n - 1, m, memory) + gridTraveler(n, m - 1, memory); | |
// Return value. | |
return memory[`${n},${m}`]; | |
} | |
console.log(gridTraveler(18, 18)); // prints => 2333606220 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment