Dynamic programming solves problems by breaking them into overlapping subproblems, solving each once, and storing the result to avoid redundant computation.

Every DP solution follows four steps:

  1. Define what dp[i] (or dp[i][j]) represents
  2. Recurrence relation — how a cell depends on previously computed cells
  3. Base cases — smallest subproblems you can answer directly
  4. Fill order — ensure dependencies are filled before they are needed

Example 1: Fibonacci

function fib($num) {
    if ($num < 0) {
        return 0;
    }

    // $dp[$i] means the i-th fibonacci number
    $dp = [];

    // $dp[0] and $dp[1] are base cases
    $dp[0] = 0;
    $dp[1] = 1;

    // fill order = left to right

    // recurrence relation: $dp[$i] = $dp[$i-1] + $dp[$i-2]
    for ($i=2; $i<=$num; $i++) {
        $dp[$i] = $dp[$i-1] + $dp[$i-2];
    }

    return $dp[$num];
}
Step Definition
dp[i] means the i-th Fibonacci number
Base cases dp[0] = 0, dp[1] = 1
Recurrence dp[i] = dp[i-1] + dp[i-2]
Fill order left to right

Walkthrough: fib(6)

Initial — base cases filled:

block-beta
  columns 7
  b0["dp[0]=0"] b1["dp[1]=1"] b2["dp[2]=?"] b3["dp[3]=?"] b4["dp[4]=?"] b5["dp[5]=?"] b6["dp[6]=?"]
  classDef base fill:#ADD8E6,stroke:#555,color:#000
  classDef unknown fill:#eee,stroke:#aaa,color:#999
  class b0,b1 base
  class b2,b3,b4,b5,b6 unknown

After filling:

block-beta
  columns 7
  b0["dp[0]=0"] b1["dp[1]=1"] b2["dp[2]=1"] b3["dp[3]=2"] b4["dp[4]=3"] b5["dp[5]=5"] b6["dp[6]=8"]
  classDef base fill:#ADD8E6,stroke:#555,color:#000
  classDef filled fill:#90EE90,stroke:#555,color:#000
  classDef answer fill:#FFD700,stroke:#555,color:#000
  class b0,b1 base
  class b2,b3,b4,b5 filled
  class b6 answer

dp[2] = dp[1] + dp[0] = 1 + 0 = 1
dp[3] = dp[2] + dp[1] = 1 + 1 = 2
dp[4] = dp[3] + dp[2] = 2 + 1 = 3
dp[5] = dp[4] + dp[3] = 3 + 2 = 5
dp[6] = dp[5] + dp[4] = 5 + 3 = 8

Answer: fib(6) = 8

Example 2: Unique Paths

A robot starts at the top-left of an m x n grid and wants to reach the bottom-right. It can only move right or down. How many unique paths are there?

function uniquePaths($rows, $cols) {
    if ($rows <= 0 || $cols <= 0) {
        return 0;
    }

    // $dp[$i][$j] means the number of unique paths to reach cell (i, j)
    $dp = [];
    for ($i=0; $i<$rows; $i++) {
        $dp[$i] = [];
        for ($j=0; $j<$cols; $j++) {
            $dp[$i][$j] = -1;
        }
    }

    // base cases:
    // $dp[$i][0] is 1 because there is only one way to go from top-left to bottom-left
    // $dp[0][$j] is 1 because there is only one way to go from top-left to top-right
    for ($i=0; $i<$rows; $i++) {
        $dp[$i][0] = 1;
    }

    for ($j=0; $j<$cols; $j++) {
        $dp[0][$j] = 1;
    }

    // fill order = left to right, top to bottom:
    // dp[i][j] always needs north and west, both already filled.

    // recurrence relation: $dp[$i][$j] = $dp[$i-1][$j] + $dp[$i][$j-1]
    for ($i=1; $i<$rows; $i++) {
        for ($j=1; $j<$cols; $j++) {
            $dp[$i][$j] = $dp[$i-1][$j] + $dp[$i][$j-1];
        }
    }

    return $dp[$rows-1][$cols-1];
}
Step Definition
dp[i][j] means number of unique paths to reach cell (i, j)
Base cases dp[0][j] = 1 (top row), dp[i][0] = 1 (left column)
Recurrence dp[i][j] = dp[i-1][j] + dp[i][j-1]
Fill order left to right, top to bottom

To reach (i, j), the robot must have come from above (i-1, j) or from the left (i, j-1).

Walkthrough: 3x3 grid

Initial — base cases filled:

block-beta
  columns 3
  b00["1"] b01["1"] b02["1"]
  b10["1"] b11["?"] b12["?"]
  b20["1"] b21["?"] b22["?"]
  classDef base fill:#ADD8E6,stroke:#555,color:#000
  classDef unknown fill:#eee,stroke:#aaa,color:#999
  class b00,b01,b02,b10,b20 base
  class b11,b12,b21,b22 unknown

After filling:

block-beta
  columns 3
  b00["1"] b01["1"] b02["1"]
  b10["1"] b11["2"] b12["3"]
  b20["1"] b21["3"] b22["6"]
  classDef base fill:#ADD8E6,stroke:#555,color:#000
  classDef filled fill:#90EE90,stroke:#555,color:#000
  classDef answer fill:#FFD700,stroke:#555,color:#000
  class b00,b01,b02,b10,b20 base
  class b11,b12,b21 filled
  class b22 answer

dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3
dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6

Answer: 6 unique paths

Example 3: Regular Expression Matching

Given string s and pattern p with . (matches any single character) and * (zero or more of the preceding character), return whether s fully matches p.

function regEx($string, $pattern) {
    // $dp[$s][$p] means whether substr($string, 0, $s) matches substr($pattern, 0, $p)
    $dp = [];
    for ($s=0; $s<=strlen($string); $s++) {
        $dp[$s] = [];
        for ($p=0; $p<=strlen($pattern); $p++) {
            $dp[$s][$p] = false;
        }
    }

    // base cases:
    // $dp[0][0] = true because empty string matches empty pattern
    // $dp[0][1] = false because empty string does not match a single letter or .
    // $dp[$s][0] = false for $s != 0 because non-empty string cannot match empty pattern
    $dp[0][0] = true;

    // fill order = left to right, top to bottom:
    // recurrence relation: $dp[$s][$p] =
        // if $pattern[$p-1] is letter:
            // if $pattern[$p-1] == $string[$s-1]: then $dp[$s-1][$p-1]
            // if $pattern[$p-1] != $string[$s-1]: then false
        // if $pattern[$p-1] is .:
            // then $dp[$s-1][$p-1]
        // if $pattern[$p-1] is *:
            // zero occurrences:     if $dp[$s][$p-2]   is true → true
            // one or more:          if $dp[$s-1][$p]   is true and preceding pattern char matches → true

    for ($s=0; $s<=strlen($string); $s++) {
        for ($p=0; $p<=strlen($pattern); $p++) {
            if ($s == 0 && $p == 0) continue;
            if ($p == 0) continue;

            if ($pattern[$p-1] != "." && $pattern[$p-1] != "*") { // letter
                if ($s == 0) continue;
                if ($pattern[$p-1] == $string[$s-1]) {
                    $dp[$s][$p] = $dp[$s-1][$p-1];
                }
                continue;
            }

            if ($pattern[$p-1] == ".") {
                if ($s == 0) continue;
                $dp[$s][$p] = $dp[$s-1][$p-1];
                continue;
            }

            if ($pattern[$p-1] == "*") {
                // zero occurrences
                if ($dp[$s][$p-2]) {
                    $dp[$s][$p] = true;
                    continue;
                }
                // one or more occurrences
                if ($s > 0 && ($pattern[$p-2] == $string[$s-1] || $pattern[$p-2] == '.') && $dp[$s-1][$p]) {
                    $dp[$s][$p] = true;
                }
            }
        }
    }

    return $dp[strlen($string)][strlen($pattern)];
}
Step Definition
dp[s][p] means whether s[:s] matches p[:p]
Base cases dp[0][0] = true; dp[0][p] = dp[0][p-2] if pattern[p-1]='*'
Recurrence depends on current pattern character (letter, ., or *)
Fill order left to right, top to bottom

Walkthrough: s = "aab", p = "a*b"

s: a(0) a(1) b(2)
p: a(0) *(1) b(2)

Initial — base cases filled:

block-beta
  columns 5
  h0[" "] h1["ε"] h2["a"] h3["*"] h4["b"]
  r0["ε"] d00["T"] d01["F"] d02["T"] d03["F"]
  r1["a"] d10["F"] d11["?"] d12["?"] d13["?"]
  r2["a"] d20["F"] d21["?"] d22["?"] d23["?"]
  r3["b"] d30["F"] d31["?"] d32["?"] d33["?"]
  classDef header fill:#ddd,stroke:#555,color:#000
  classDef base fill:#ADD8E6,stroke:#555,color:#000
  classDef unknown fill:#eee,stroke:#aaa,color:#999
  class h0,h1,h2,h3,h4,r0,r1,r2,r3 header
  class d00,d02,d10,d20,d30 base
  class d01,d03 base
  class d11,d12,d13,d21,d22,d23,d31,d32,d33 unknown

After filling:

block-beta
  columns 5
  h0[" "] h1["ε"] h2["a"] h3["*"] h4["b"]
  r0["ε"] d00["T"] d01["F"] d02["T"] d03["F"]
  r1["a"] d10["F"] d11["T"] d12["T"] d13["F"]
  r2["a"] d20["F"] d21["F"] d22["T"] d23["F"]
  r3["b"] d30["F"] d31["F"] d32["F"] d33["T"]
  classDef header fill:#ddd,stroke:#555,color:#000
  classDef base fill:#ADD8E6,stroke:#555,color:#000
  classDef t fill:#90EE90,stroke:#555,color:#000
  classDef answer fill:#FFD700,stroke:#555,color:#000
  class h0,h1,h2,h3,h4,r0,r1,r2,r3 header
  class d00,d02,d10,d20,d30 base
  class d11,d12,d22 t
  class d33 answer

Key cells explained:

Cell Pattern char Rule Depends on Result
dp[0][2] * zero occurrences: dp[0][0]=T dp[0][0] T
dp[1][1] a a==a, diagonal dp[0][0]=T T
dp[1][2] * one or more: a==a, north dp[0][2]=T T
dp[2][2] * one or more: a==a, north dp[1][2]=T T
dp[3][3] b b==b, diagonal dp[2][2]=T T

Answer: true — "aab" matches "a*b"