Probability & Game-Theoretic Dynamic Programming

1. Introduction & Motivation

Every dynamic programming solution has two ingredients: a state, and a recursion that combines the answers of smaller states into the answer for a larger one. Most introductory DP problems optimize a single deterministic quantity — the minimum number of coins, the longest common subsequence, the maximum subset sum. The combination step is min, max, or a count, and the transition is deterministic: from state $s$, exactly one specific next state follows for each choice.

This lesson covers two variants that keep the same DP skeleton — define a state, write a recursion, fill states in dependency order — but change what the state stores and how transitions combine:

• Expectation / probability DP: the state stores an expected value or a probability, computed as a weighted sum averaged over random outcomes rather than a min or max over choices.
• Game DP: the state stores a win/lose verdict (or an optimal score) computed under the assumption that an adversary always makes the move that is worst for you.

Both variants show up constantly in practice: expected-value DP models reliability, expected cost, and randomized processes; game DP is the backbone of solvers for combinatorial games, and its numeric generalization, minimax, is the same idea used to evaluate positions in chess and Go engines.

2. Prerequisites

This lesson assumes comfort with general DP methodology — states, recursions, memoization versus tabulation, and dependency ordering — as covered in DSA Part 14: Dynamic Programming Foundations. If you are already comfortable exploring recursive game/search trees by hand, DSA Part 17: Backtracking & Constraint Search covers the general recursive search-tree framing that game DP later collapses with memoization; this lesson does not re-derive that mechanics.

3. Core Insight: Expected Value DP

$$dp[state] = \sum_{next\_state} P(next\_state \mid state) \times \big(cost + dp[next\_state]\big)$$

Because the right-hand side sums over all possible outcomes rather than picking one, expectation DP has no notion of a "best" transition — every outcome that can happen contributes to the average, weighted by how likely it is.

Ordering still matters. Just like ordinary DP, the recursion must be evaluated in an order where every $dp[next\_state]$ used on the right-hand side is already known. Usually this means working backward from a terminal or absorbing state (a state with no further transitions, where the expectation is a known base case such as 0).

Caveat — self-referential states: in some random-walk-shaped problems, a state's own probability of transitioning back to itself makes $dp[state]$ appear on both sides of its own equation (for example, "roll again and stay in the same state with probability $p$"). This is not a bug in the recursion — it means the equation for that state is a genuine algebraic equation, not a lookup, and must be solved for $dp[state]$ before it is stored in the table. In the simplest cases (see Section 5) this is a one-line rearrangement. In more tangled random walks with cycles between several mutually dependent states, the fix is to solve a small system of linear equations instead of filling the table left to right — a caveat worth recognizing, even though the examples below never require solving a full system.

4. A Concrete Example

5. Expected Value in Practice

The worked example above never revisits a state, which kept it simple. The next three examples show the full pattern in code: a self-referential expected-value recursion solved by algebra, the same DP run forward to track a probability instead of an expectation, and a stopping-time framing of the same idea.

Dice/Coin Problems: The Coupon Collector

How many rolls of a fair 6-sided die are expected before every one of the 6 faces has appeared at least once? Let $dp[k]$ be the expected number of additional rolls needed once $k$ distinct faces have already been seen. A new roll shows an already-seen face with probability $k/6$ (progress does not change) or a new face with probability $(6-k)/6$ (progress advances to $k+1$):

$$dp[k] = 1 + \frac{k}{6}\,dp[k] + \frac{6-k}{6}\,dp[k+1]$$

This is exactly the self-referential case from Section 3's caveat: $dp[k]$ appears on both sides. Solving algebraically first ($dp[k]$ minus its own coefficient, moved to the left):

$$dp[k] = \frac{6}{6-k} + dp[k+1], \qquad dp[6] = 0$$

Only after this rearrangement is the recursion a plain table lookup, filled backward from $dp[6]=0$ down to $dp[0]$. Hand-tracing: $dp[5]=6$, $dp[4]=9$, $dp[3]=11$, $dp[2]=12.5$, $dp[1]=13.7$, $dp[0]=14.7$ — matching the closed form $6H_6 = 6(1+\tfrac12+\tfrac13+\tfrac14+\tfrac15+\tfrac16) = 14.7$.

def expected_rolls_to_see_all_faces(n=6):
    """Expected number of rolls of a fair n-sided die to see every
    face at least once (the Coupon Collector problem)."""
    dp = [0.0] * (n + 1)   # dp[k] = expected additional rolls, k faces seen
    dp[n] = 0.0            # all faces seen: no more rolls needed
    for k in range(n - 1, -1, -1):
        # Naive: dp[k] = 1 + (k/n)*dp[k] + ((n-k)/n)*dp[k+1]
        # dp[k] appears on both sides -- solve algebraically first:
        # dp[k] * (n-k)/n = 1 + ((n-k)/n) * dp[k+1]
        # dp[k] = n/(n-k) + dp[k+1]
        dp[k] = n / (n - k) + dp[k + 1]
    return dp[0]

print(f"{expected_rolls_to_see_all_faces(6):.4f}")  # 14.7000

#include <iostream>
#include <vector>

double expectedRollsToSeeAllFaces(int n) {
    std::vector<double> dp(n + 1, 0.0);
    dp[n] = 0.0;
    for (int k = n - 1; k >= 0; --k) {
        dp[k] = static_cast<double>(n) / (n - k) + dp[k + 1];
    }
    return dp[0];
}

int main() {
    std::cout << expectedRollsToSeeAllFaces(6) << '\n'; // 14.7
}

public class CouponCollector {
    static double expectedRollsToSeeAllFaces(int n) {
        double[] dp = new double[n + 1];
        dp[n] = 0.0;
        for (int k = n - 1; k >= 0; k--) {
            dp[k] = (double) n / (n - k) + dp[k + 1];
        }
        return dp[0];
    }

    public static void main(String[] args) {
        System.out.println(expectedRollsToSeeAllFaces(6)); // 14.7
    }
}

Probability Transitions: Knight's Probability

A different flavor: instead of an expected value, compute the probability of ending in a particular state after a fixed number of random steps. Let $dp[step][r][c]$ be the probability a knight is at square $(r,c)$ after step random moves on an $n \times n$ board, starting from a fixed square. Unlike the backward reasoning above, this DP is propagated forward: each state pushes $\frac{1}{8}$ of its own probability mass onto every one of its (up to 8) knight-move neighbors, and moves that land off the board simply lose that probability mass (the knight "fell off" and never returns).

$$dp[step+1][r'][c'] \mathrel{+{=}} dp[step][r][c] \times \tfrac{1}{8} \quad \text{for every in-bounds knight move } (r,c) \to (r',c')$$

The answer — the probability the knight is still on the board after $k$ moves — is the sum of $dp[k][r][c]$ over every square.

def knight_probability(n, k, row, column):
    """Probability a knight remains on an n x n board after k random
    moves, starting at (row, column). All 8 knight moves are equally
    likely; a move off the board ends that fraction of the walk."""
    moves = [(-2, -1), (-2, 1), (-1, -2), (-1, 2),
             (1, -2), (1, 2), (2, -1), (2, 1)]
    dp = [[0.0] * n for _ in range(n)]
    dp[row][column] = 1.0
    for _ in range(k):
        next_dp = [[0.0] * n for _ in range(n)]
        for r in range(n):
            for c in range(n):
                prob = dp[r][c]
                if prob == 0.0:
                    continue
                for dr, dc in moves:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n:
                        next_dp[nr][nc] += prob / 8.0
        dp = next_dp
    return sum(sum(row_probs) for row_probs in dp)

print(f"{knight_probability(8, 3, 0, 0):.4f}")  # 0.0625

#include <iostream>
#include <vector>

double knightProbability(int n, int k, int row, int column) {
    static const int moves[8][2] = {
        {-2,-1}, {-2,1}, {-1,-2}, {-1,2},
        {1,-2}, {1,2}, {2,-1}, {2,1}
    };
    std::vector<std::vector<double>> dp(n, std::vector<double>(n, 0.0));
    dp[row][column] = 1.0;
    for (int step = 0; step < k; ++step) {
        std::vector<std::vector<double>> next(n, std::vector<double>(n, 0.0));
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                double prob = dp[r][c];
                if (prob == 0.0) continue;
                for (auto& mv : moves) {
                    int nr = r + mv[0], nc = c + mv[1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                        next[nr][nc] += prob / 8.0;
                    }
                }
            }
        }
        dp = next;
    }
    double total = 0.0;
    for (auto& row_probs : dp)
        for (double p : row_probs) total += p;
    return total;
}

int main() {
    std::cout << knightProbability(8, 3, 0, 0) << '\n'; // 0.0625
}

public class KnightProbability {
    static double knightProbability(int n, int k, int row, int column) {
        int[][] moves = {
            {-2,-1}, {-2,1}, {-1,-2}, {-1,2},
            {1,-2}, {1,2}, {2,-1}, {2,1}
        };
        double[][] dp = new double[n][n];
        dp[row][column] = 1.0;
        for (int step = 0; step < k; step++) {
            double[][] next = new double[n][n];
            for (int r = 0; r < n; r++) {
                for (int c = 0; c < n; c++) {
                    double prob = dp[r][c];
                    if (prob == 0.0) continue;
                    for (int[] mv : moves) {
                        int nr = r + mv[0], nc = c + mv[1];
                        if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                            next[nr][nc] += prob / 8.0;
                        }
                    }
                }
            }
            dp = next;
        }
        double total = 0.0;
        for (double[] rowProbs : dp)
            for (double p : rowProbs) total += p;
        return total;
    }

    public static void main(String[] args) {
        System.out.println(knightProbability(8, 3, 0, 0)); // 0.0625
    }
}

Expected Stopping Time

"Expected number of steps until some stopping condition is met" is exactly the expected-value DP from this section, framed with a state that tracks progress toward the stopping condition. The Coupon Collector recursion above is itself a stopping-time DP: the stopping condition is "all $n$ faces seen", the state is the progress counter $k$, and $dp[0]$ is the expected stopping time from no progress at all. The same recursion generalizes directly to a stopping condition met before every face has been seen — stop once $k$ out of $n$ distinct faces have appeared, for $k \le n$:

$$dp[progress] = \frac{n}{n-progress} + dp[progress+1], \qquad dp[k] = 0$$

def expected_rolls_to_see_k_faces(n, k):
    """Expected number of rolls of a fair n-sided die until k distinct
    faces (k <= n) have been seen. State = progress toward the
    stopping condition; dp[progress] = expected remaining rolls."""
    dp = [0.0] * (k + 1)
    dp[k] = 0.0  # stopping condition already met
    for progress in range(k - 1, -1, -1):
        # Same self-referential pattern as the full Coupon Collector,
        # solved the same way: dp[p]=1+(p/n)dp[p]+((n-p)/n)dp[p+1]
        # rearranges to dp[p] = n/(n-p) + dp[p+1]
        dp[progress] = n / (n - progress) + dp[progress + 1]
    return dp[0]

print(f"{expected_rolls_to_see_k_faces(6, 4):.4f}")  # 5.7000

#include <iostream>
#include <vector>

double expectedRollsToSeeKFaces(int n, int k) {
    std::vector<double> dp(k + 1, 0.0);
    dp[k] = 0.0;
    for (int progress = k - 1; progress >= 0; --progress) {
        dp[progress] = static_cast<double>(n) / (n - progress) + dp[progress + 1];
    }
    return dp[0];
}

int main() {
    std::cout << expectedRollsToSeeKFaces(6, 4) << '\n'; // 5.7
}

public class ExpectedStoppingTime {
    static double expectedRollsToSeeKFaces(int n, int k) {
        double[] dp = new double[k + 1];
        dp[k] = 0.0;
        for (int progress = k - 1; progress >= 0; progress--) {
            dp[progress] = (double) n / (n - progress) + dp[progress + 1];
        }
        return dp[0];
    }

    public static void main(String[] args) {
        System.out.println(expectedRollsToSeeKFaces(6, 4)); // 5.7
    }
}

6. Core Insight: Game DP (Winning/Losing States)

This is the fundamental recursive definition underlying Grundy-number and Nim-style game analysis: a position is winning if the player to move can hand the opponent a losing position, and losing if every available move hands the opponent a winning position. Unlike expectation DP, there is no averaging — the combination rule is an existential quantifier over moves ("does some move lead to LOSE?"), which behaves like a max/min over a boolean-valued function.

A small combinatorial game makes this concrete: two players alternately remove 1, 3, or 4 stones from a pile of $n$ stones; the player who removes the last stone wins. Let $dp[i]=\text{true}$ mean the player about to move with $i$ stones remaining wins with optimal play. The base case $dp[0]=\text{false}$: with no stones left, the player to move has no legal move and loses (the previous player took the last stone and won).

$$dp[i] = \exists\, m \in \{1,3,4\},\ m \le i,\ \text{such that } dp[i-m] = \text{false}$$

Hand-tracing from $dp[0]$ upward: $dp[1]{=}\text{T}$ (remove 1 → $dp[0]{=}\text{F}$), $dp[2]{=}\text{F}$ (only move is remove 1 → $dp[1]{=}\text{T}$), $dp[3]{=}\text{T}$ (remove 1 → $dp[2]{=}\text{F}$), $dp[4]{=}\text{T}$, $dp[5]{=}\text{T}$, $dp[6]{=}\text{T}$, then $dp[7]{=}\text{F}$ — at 7 stones, removing 1, 3, or 4 leaves 6, 4, or 3 stones, and $dp[6]=dp[4]=dp[3]=\text{T}$ for all of them, so every move hands the opponent a win.

def first_player_wins(n, moves=(1, 3, 4)):
    """Players alternately remove 1, 3, or 4 stones from a pile of n;
    the player who removes the last stone wins. Returns True if the
    player about to move at pile size n wins with optimal play."""
    dp = [False] * (n + 1)  # dp[i] = True if the mover at pile i wins
    dp[0] = False            # no stones left: the mover cannot move, loses
    for i in range(1, n + 1):
        for m in moves:
            if m <= i and not dp[i - m]:
                dp[i] = True
                break
    return dp[n]

for pile in (7, 8):
    mover_wins = first_player_wins(pile)
    print(f"Pile of {pile}: {'mover' if mover_wins else 'other player'} wins")
# Pile of 7: other player wins   (dp[7] = False)
# Pile of 8: mover wins          (dp[8] = True)

#include <iostream>
#include <vector>

bool firstPlayerWins(int n) {
    static const int moves[3] = {1, 3, 4};
    std::vector<bool> dp(n + 1, false);
    dp[0] = false;
    for (int i = 1; i <= n; ++i) {
        for (int m : moves) {
            if (m <= i && !dp[i - m]) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}

int main() {
    std::cout << std::boolalpha;
    std::cout << "Pile of 7, mover wins: " << firstPlayerWins(7) << '\n'; // false
    std::cout << "Pile of 8, mover wins: " << firstPlayerWins(8) << '\n'; // true
}

public class SubtractionGame {
    static boolean firstPlayerWins(int n) {
        int[] moves = {1, 3, 4};
        boolean[] dp = new boolean[n + 1];
        dp[0] = false;
        for (int i = 1; i <= n; i++) {
            for (int m : moves) {
                if (m <= i && !dp[i - m]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println("Pile of 7, mover wins: " + firstPlayerWins(7)); // false
        System.out.println("Pile of 8, mover wins: " + firstPlayerWins(8)); // true
    }
}

Minimax on Finite State Trees

Win/lose games generalize to games with numeric scores, where one player maximizes and the other minimizes the same underlying value: $dp[state][turn] = \max$ or $\min$ over moves of $dp[next\_state]$, depending on whose turn it is. A common simplification avoids tracking whose turn it is explicitly: since both players are maximizing their own score, define $dp[i][j]$ as the best score difference (current player's score minus the opponent's) achievable from the remaining sub-array piles[i..j]. Whichever player is "current" always wants to maximize this difference, so a single max suffices at every state:

$$dp[i][j] = \max\big(piles[i] - dp[i+1][j],\ piles[j] - dp[i][j-1]\big), \qquad dp[i][i] = piles[i]$$

Taking a pile scores $piles[i]$ for the current player, but flips perspective for the remaining sub-array — hence the subtraction. Hand-tracing on [3, 9, 1, 2]: base cases give $dp[i][i]=$ 3, 9, 1, 2. Length-2: $dp[0][1]=\max(3-9,9-3)=6$, $dp[1][2]=\max(9-1,1-9)=8$, $dp[2][3]=\max(1-2,2-1)=1$. Length-3: $dp[0][2]=\max(3-8,1-6)=-5$, $dp[1][3]=\max(9-1,2-8)=8$. Length-4: $dp[0][3]=\max(3-8,\,2-(-5))=\max(-5,7)=7$. A positive margin of 7 means the first player wins by 7 points with optimal play from both sides.

def predict_winner_margin(piles):
    """Two players alternately take a pile from either end of the array
    to maximize their own total. dp[i][j] is the best score difference
    (current player's score minus the opponent's) from piles[i..j]."""
    n = len(piles)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = piles[i]
    for length in range(2, n + 1):
        for i in range(0, n - length + 1):
            j = i + length - 1
            dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
    return dp[0][n - 1]

sample = [3, 9, 1, 2]
margin = predict_winner_margin(sample)
print(f"Score margin for the first player: {margin}")  # 7
print("First player wins" if margin > 0 else "Second player wins or ties")

#include <algorithm>
#include <iostream>
#include <vector>

int predictWinnerMargin(const std::vector<int>& piles) {
    int n = piles.size();
    std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
    for (int i = 0; i < n; ++i) dp[i][i] = piles[i];
    for (int length = 2; length <= n; ++length) {
        for (int i = 0; i + length - 1 < n; ++i) {
            int j = i + length - 1;
            dp[i][j] = std::max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
        }
    }
    return dp[0][n - 1];
}

int main() {
    std::vector<int> sample{3, 9, 1, 2};
    std::cout << "Score margin: " << predictWinnerMargin(sample) << '\n'; // 7
}

public class PredictWinner {
    static int predictWinnerMargin(int[] piles) {
        int n = piles.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) dp[i][i] = piles[i];
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i + length - 1 < n; i++) {
                int j = i + length - 1;
                dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        int[] sample = {3, 9, 1, 2};
        System.out.println("Score margin: " + predictWinnerMargin(sample)); // 7
    }
}

Interval Games

Notice that the Predict-the-Winner recursion above is indexed by $dp[i][j]$ — the remaining contiguous sub-array both players can still choose from. That is exactly the interval DP shape: the state is a range $[i,j]$ over a sequence, and the recursion combines the two ways to shrink the range from either end. Many minimax games played on an array or sequence reduce to interval DP in this way. DSA: Interval DP covers that general mental model — state defined over sub-array bounds, transitions that pick an endpoint, and the $O(n^2)$ table of ranges — in depth; this lesson only makes the connection explicit rather than re-deriving it.

7. Complexity Analysis

8. Applications & Alternatives

9. Exercises and Mastery

Easy

1. Adapt the worked example in Section 4 to compute the expected number of rolls for the running sum to reach at least 5, and hand-trace the table down to $dp[0]$.

Medium

1. Using the Knight's Probability code, compute the probability a knight starting at the center of a 6×6 board is still on the board after 2 moves.

Hard

1. Using the Predict-the-Winner code, determine which player wins [1, 5, 2, 4, 6] with optimal play, and by how many points. Trace at least the base cases and one length-3 state by hand before checking the code's output.

Review rhythm: tomorrow, re-derive the Coupon Collector's algebraic rearrangement from the naive self-referential recursion without notes; next week, implement Predict-the-Winner from scratch and verify it against the hand trace above; several weeks later, identify a real system (a queue, a game, a retry policy) where the DP state should store an expectation or a win/lose verdict instead of a min or max, and write down why.

10. Summary Cheat Sheet

• Standard DP optimizes a deterministic value; these variants change what the state stores.
• Expected-value DP: $dp[state] = \sum P(next) \times (cost + dp[next])$, a probability-weighted sum, not a min/max.
• Self-referential expectation states (a transition back to the same state) require solving a small algebraic equation before the value can be stored, not a plain lookup.
• Probability-transition DP runs forward: $dp[step][state]$ propagates probability mass to future steps, unlike expectation DP's usual backward reasoning.
• Expected stopping time is expectation DP where the state tracks progress toward a stopping condition.
• Game DP: $dp[state] = \text{WIN}$ if some move reaches a $\text{LOSE}$ state for the opponent; $\text{LOSE}$ if every move reaches a $\text{WIN}$ state for the opponent.
• Minimax generalizes win/lose to numeric scores: $dp[state][turn] = \max$ or $\min$ over moves, depending on whose turn it is.
• Many array/sequence minimax games reduce to interval DP over sub-array bounds $[i,j]$.
• Complexity stays states × transitions for both families — only the per-state arithmetic changes.