#576. Out of Boundary Paths

https://leetcode.com/problems/out-of-boundary-paths/description/?envType=daily-question&envId=2024-01-26

var findPaths = function (m, n, maxMove, startRow, startColumn) {
    const mod = 10 ** 9 + 7
    const cache = {}

    function dfs(row, col, moves) {
        if (row < 0 || row === m || col < 0 || col === n) return 1

        if (moves === 0) return 0

        if (`${row}-${col}-${moves}` in cache) return cache[`${row}-${col}-${moves}`]

        cache[`${row}-${col}-${moves}`] = (
            (dfs(row + 1, col, moves - 1) + dfs(row - 1, col, moves - 1)) % mod
            + (dfs(row, col + 1, moves - 1) + dfs(row, col - 1, moves - 1)) % mod
        ) % mod

        return cache[`${row}-${col}-${moves}`]
    }

    return dfs(startRow, startColumn, maxMove)
};

An easy medium.

When the grid is out of bounds and there are still moves, return one.

If there are zero moves, return zero.

Then go through all four sides of a gird and all the four sides neighbour grids and use dynamic programming to make it optimized.

The modulus of the answer is returned because value can get too high.