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

$ curl repovive.com/roadmaps/dynamic-programming/probability-dp/knight-probability-implementation

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

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

$ curl repovive.com/roadmaps/dynamic-programming/probability-dp/knight-probability-implementation

Repovive

Knight Probability - Implementation - Probability DP | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

Knight Probability - Implementation

The code

Here's the solution with caching (to avoid recomputing the same dp values):

function knightProbability(n, k, row, col)
    dp := 3D array [n][n][k + 1], all -1
    return solve(row, col, k, n)
function solve(r, c, k, n)
    if r < 0 or r >= n or c < 0 or c >= n then
        return 0
    if k = 0 then
        return 1
    if dp[r][c][k] ≠ -1 then
        return dp[r][c][k]
    moves := [(-2,-1),(-2,1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1)]
    prob := 0
    for (dr, dc) in moves
        prob := prob + solve(r + dr, c + dc, k - 1, n) / 8
    dp[r][c][k] := prob
    return prob

Time: $O(n^2 \cdot k)$ with array-based memoization. Space: $O(n^2 \cdot k)$ .

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