#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/probability-dp/out-of-boundary-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/probability-dp/out-of-boundary-implementation

Repovive

Out of Boundary - Implementation - Probability DP | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

Out of Boundary - Implementation

The code

Here's the memoized solution:

function findPaths
    MOD := 10^9 + 7
    dp := 3D (three-dimensional) array [m][n][maxMove + 1], all -1
    return solve
function solve(r, c, k, m, n, MOD)
    if r < 0 or r >= m or c < 0 or c >= n then
        return 1
    if k = 0 then
        return 0
    if dp[r][c][k] ≠ -1 then
        return dp[r][c][k]
    result := 0
    result := (result + solve(r - 1, c, k - 1, m, n, MOD)) % MOD
    result := (result + solve(r + 1, c, k - 1, m, n, MOD)) % MOD
    result := (result + solve(r, c - 1, k - 1, m, n, MOD)) % MOD
    result := (result + solve(r, c + 1, k - 1, m, n, MOD)) % MOD
    dp[r][c][k] := result
    return result

Leaving the grid returns $1$ . Staying with no moves returns $0$ . Sum over $4$ directions, modulo $10^9 + 7$ .

Time: $O(m \cdot n \cdot k)$ . Space: $O(m \cdot n \cdot k)$ .

Time: $O(N \cdot m \cdot n)$ . Space: $O(m \cdot n)$ .