4. Dynamic Programming#

For all $i \in {1, \ldots, n}$, let $\mathsf{OPT}[i]$ denote the sum of $A[1 ,:, i]$; we will return $\mathsf{OPT}[n]$. The base case is $\mathsf{OPT}[1] = A[1]$, and the recurrence is $\mathsf{OPT}[i] = \mathsf{OPT}[i-1] + A[i]$. The recurrence holds because the sum of $A[1 ,:, i]$ is equal to the sum of $A[1 ,:, i-1]$ plus $A[i]$. The pseudocode is below:

ALG(A):
  d = [A[1]]*n
  for i = 2, ..., n:
    d[i] = d[i-1] + A[i]
  return d[n]

The algorithm makes $n-1$ iterations and each takes $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 674.) For all $i \in {1, \ldots, n}$, let $\mathsf{OPT}[i]$ denote the length of the longest contiguous increasing subsequence in $A[1 ,:, i]$ that must end on $A[i]$; we will return $\max(\mathsf{OPT})$. The base case is $\mathsf{OPT}[1] = 1$, and the recurrence is:

$$\mathsf{OPT}[i] = 1 + \begin{cases} \mathsf{OPT}[i-1] & \text{if } A[i] > A[i-1] \ 0 & \text{otherwise.} \end{cases}$$

The recurrence holds because the longest increasing subarray that ends on $A[i]$ must include $A[i]$ (hence the “$1$”) as well as possibly, if $A[i] > A[i-1]$, a portion that ends on $A[i-1]$; $\mathsf{OPT}[i-1]$ is the maximum length of that portion. The pseudocode is below:

ALG(A):
  d = [1] * n
  for i = 2, ..., n:
    if A[i] > A[i-1]:
      d[i] += d[i-1]
  return max(d)

The algorithm makes $n-1$ iterations and each takes $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 746.) For all $i \in {1, \ldots, n}$, let $\mathsf{OPT}[i]$ denote the minimum cost to stop on $A[i]$, so $\mathsf{OPT}[1] = A[1]$, $\mathsf{OPT}[2] = A[2]$, and we want to return $\min(\mathsf{OPT}[n-1], \mathsf{OPT}[n])$ (since we could jump to $n+1$ from either index $n-1$ or $n$). For all $i \in {3, \ldots, n}$, to land on $A[i]$ we could jump from either $A[i-2]$ or $A[i-1]$ (whichever is cheaper), and we must pay $A[i]$, so:

$$\mathsf{OPT}[i] = \min(\mathsf{OPT}[i-2], \mathsf{OPT}[i-1]) + A[i].$$

The pseudocode is below:

ALG(A):
  d = [A[1]]*n
  d[2] = A[2]
  for i = 3, ..., n:
    d[i] = min(d[i-2], d[i-1]) + A[i]
  return min(d[n-1], d[n])

The algorithm makes $O(n)$ iterations and each takes $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 63.) For all $i \in {1, \ldots, m}$ and $j \in {1, \ldots, n}$, let $\mathsf{OPT}[i][j]$ denote the number of paths from $(1, 1)$ to $(i, j)$; we want to return $\mathsf{OPT}[m][n]$. In row $i = 1$, there is exactly one path to $(1, j)$ until we hit an obstacle (after which there are $0$ paths). Similar logic holds for column $j = 1$.

For all $i, j \geq 2$, to reach $(i,j)$ we can arrive from either $(i-1, j)$ or $(i, j-1)$:

$$\mathsf{OPT}[i][j] = \begin{cases} \mathsf{OPT}[i-1][j] + \mathsf{OPT}[i][j-1] & \text{if } A[i][j] = 0 \ 0 & \text{otherwise.} \end{cases}$$

The pseudocode is below:

ALG(A):
  d = [0] * (m rows, n columns)
  for j = 1, ..., n:     # first row
    if A[1][j] = 0: d[1][j] = 1
    else: break
  for i = 1, ..., m:     # first column
    if A[i][1] = 0: d[i][1] = 1
    else: break
  for i = 2, ..., m:
    for j = 2, ..., n:
      if A[i][j] = 0:
        d[i][j] += d[i-1][j] + d[i][j-1]
  return d[m][n]

Every iteration in every loop takes $O(1)$ time, so the total running time is $O(n) + O(m) + O(mn) = O(mn)$.

(This is LeetCode 121.) For all $j \in {2, \ldots, n}$, let $\mathsf{OPT}[j]$ denote the maximum profit if we had to sell on day $j$. Then $\mathsf{OPT}[j] = A[j] - \min_{i < j} A[i]$. This appears to yield an $O(n^2)$-time algorithm ($n$ subproblems, $O(n)$ time each), but we can implement it in $O(n)$ time by updating $\min_{i < j} A[i]$ as $j$ increases:

ALG(A):
  min_A = A[1]
  d = [-inf] * n
  for j = 2, ..., n:
    d[j] = A[j] - min_A
    min_A = min(min_A, A[j])
  return max(d)

The algorithm makes $O(n)$ iterations and each takes $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 198.) For all $i \in {1, \ldots, n}$, let $\mathsf{OPT}[i]$ denote the largest feasible sum given $A[1 ,:, i]$. So $\mathsf{OPT}[1] = A[1]$, $\mathsf{OPT}[2] = \max(A[1], A[2])$, and we want to return $\mathsf{OPT}[n]$. For all $i \in {3, \ldots, n}$:

$$\mathsf{OPT}[i] = \max(\mathsf{OPT}[i-1],; A[i] + \mathsf{OPT}[i-2]).$$

This is because the optimal subsequence in $A[1 ,:, i]$ either excludes $A[i]$ (value $\mathsf{OPT}[i-1]$) or includes $A[i]$ (value $A[i] + \mathsf{OPT}[i-2]$, since $A[i-1]$ cannot also be included).

ALG(A):
  if n = 1: return A[1]
  if n = 2: return max(A[1], A[2])
  d = [A[1]] * n
  d[2] = max(A[1], A[2])
  for i = 3, ..., n:
    d[i] = max(d[i-1], A[i] + d[i-2])
  return d[n]

The algorithm makes $O(n)$ iterations and each takes $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 2466.) For all $i \in {0, 1, \ldots, n}$, let $\mathsf{OPT}[i]$ denote the number of ways to reach $i$, so $\mathsf{OPT}[0] = 1$ and we return $\mathsf{OPT}[n]$. For all $i \geq 1$:

$$\mathsf{OPT}[i] = \mathsf{OPT}[i-A] + \mathsf{OPT}[i-B],$$

where $\mathsf{OPT}[j] = 0$ for all $j < 0$. This holds because any way of reaching $i$ must end with either $A$ or $B$, so the count is the number of ways to reach $i - A$ plus the number of ways to reach $i - B$.

ALG(A, B, n):
  d = [0] * (n+1)  # d starts at index 0
  d[0] = 1
  for i = 1, 2, ..., n:
    if i - A >= 0:
      d[i] += d[i-A]
    if i - B >= 0:
      d[i] += d[i-B]
  return d[n]

The algorithm makes $O(n)$ iterations and each takes $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 53.) For all $i \in {1, \ldots, n}$, let $\mathsf{OPT}[i]$ denote the maximum subarray sum ending at index $i$; we return $\max(\mathsf{OPT})$. The base case is $\mathsf{OPT}[1] = A[1]$, and the recurrence is:

$$\mathsf{OPT}[i] = \max(A[i],; \mathsf{OPT}[i-1] + A[i]).$$

The best subarray ending at $A[i]$ either starts fresh at $i$ or extends the best subarray ending at $i-1$.

ALG(A):
  d = [A[1]] * n
  for i = 2, ..., n:
    d[i] = max(A[i], d[i-1] + A[i])
  return max(d)

The algorithm makes $n-1$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 152.) We track both the maximum and minimum product ending at each index, because a negative times a negative can produce a new maximum. Let $\mathsf{MX}[i]$ and $\mathsf{MN}[i]$ be the max and min product of a subarray ending at $A[i]$. The base cases are $\mathsf{MX}[1] = \mathsf{MN}[1] = A[1]$, and the recurrences are:

$$\mathsf{MX}[i] = \max(A[i],; A[i] \cdot \mathsf{MX}[i-1],; A[i] \cdot \mathsf{MN}[i-1])$$ $$\mathsf{MN}[i] = \min(A[i],; A[i] \cdot \mathsf{MX}[i-1],; A[i] \cdot \mathsf{MN}[i-1])$$

We return $\max(\mathsf{MX})$. If $A[i] > 0$, the max comes from extending the previous max; if $A[i] < 0$, it may come from extending the previous min.

ALG(A):
  mx = [A[1]] * n
  mn = [A[1]] * n
  for i = 2, ..., n:
    mx[i] = max(A[i], A[i]*mx[i-1], A[i]*mn[i-1])
    mn[i] = min(A[i], A[i]*mx[i-1], A[i]*mn[i-1])
  return max(mx)

The algorithm makes $n-1$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 918.) The answer is either a normal (non-wrapping) max subarray, or a wrapping subarray whose sum equals $\text{sum}(A) - \text{minSubarray}(A)$. If all elements are negative, the wrapping case gives $0$, so we return the normal max instead.

ALG(A):
  maxHere, minHere = A[1], A[1]
  bestMax, bestMin, total = A[1], A[1], A[1]
  for i = 2, ..., n:
    maxHere = max(A[i], maxHere + A[i])
    minHere = min(A[i], minHere + A[i])
    bestMax = max(bestMax, maxHere)
    bestMin = min(bestMin, minHere)
    total += A[i]
  if bestMax < 0:
    return bestMax
  return max(bestMax, total - bestMin)

We compute max subarray and min subarray simultaneously in one pass. The algorithm makes $n-1$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 300.) For all $i \in {1, \ldots, n}$, let $\mathsf{OPT}[i]$ denote the length of the longest increasing subsequence ending at $A[i]$; we return $\max(\mathsf{OPT})$. Initialize $\mathsf{OPT}[i] = 1$ for all $i$. The recurrence is:

$$\mathsf{OPT}[i] = 1 + \max_{j < i,; A[j] < A[i]} \mathsf{OPT}[j]$$

(or just $1$ if no such $j$ exists). Any increasing subsequence ending at $A[i]$ must have a previous element $A[j]$ with $j < i$ and $A[j] < A[i]$; we pick the best such $j$.

ALG(A):
  d = [1] * n
  for i = 2, ..., n:
    for j = 1, ..., i-1:
      if A[j] < A[i]:
        d[i] = max(d[i], d[j] + 1)
  return max(d)

There are $n$ subproblems each taking $O(n)$ time, so the total running time is $O(n^2)$.

(This is LeetCode 673.) For all $i$, let $\mathsf{LEN}[i]$ = length of LIS ending at $A[i]$, and $\mathsf{CNT}[i]$ = number of such subsequences. Initialize $\mathsf{LEN}[i] = 1$ and $\mathsf{CNT}[i] = 1$. For each $j < i$ with $A[j] < A[i]$: if $\mathsf{LEN}[j] + 1 > \mathsf{LEN}[i]$, update $\mathsf{LEN}[i] = \mathsf{LEN}[j] + 1$ and $\mathsf{CNT}[i] = \mathsf{CNT}[j]$; if $\mathsf{LEN}[j] + 1 = \mathsf{LEN}[i]$, add $\mathsf{CNT}[j]$ to $\mathsf{CNT}[i]$.

ALG(A):
  len = [1] * n
  cnt = [1] * n
  for i = 2, ..., n:
    for j = 1, ..., i-1:
      if A[j] < A[i]:
        if len[j] + 1 > len[i]:
          len[i] = len[j] + 1
          cnt[i] = cnt[j]
        else if len[j] + 1 = len[i]:
          cnt[i] += cnt[j]
  L = max(len)
  return sum of cnt[i] for all i where len[i] = L

There are $n$ subproblems each taking $O(n)$ time, so the total running time is $O(n^2)$.

(This is LeetCode 376.) Maintain two values: $\mathsf{UP}$ = length of longest wiggle ending with an upward move, and $\mathsf{DOWN}$ = length ending with a downward move. Initialize both to $1$. For $i = 2, \ldots, n$: if $A[i] > A[i-1]$, set $\mathsf{UP} = \mathsf{DOWN} + 1$; if $A[i] < A[i-1]$, set $\mathsf{DOWN} = \mathsf{UP} + 1$.

An upward move can only extend a sequence that last went down, and vice versa, so this correctly captures the alternation.

ALG(A):
  up, down = 1, 1
  for i = 2, ..., n:
    if A[i] > A[i-1]:
      up = down + 1
    else if A[i] < A[i-1]:
      down = up + 1
  return max(up, down)

The algorithm makes $n-1$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 978.) Let $\mathsf{INC}[i]$ = length of turbulent subarray ending at $i$ where $A[i] > A[i-1]$, and $\mathsf{DEC}[i]$ = length where $A[i] < A[i-1]$. Initialize both to $1$.

If $A[i] > A[i-1]$: $\mathsf{INC}[i] = \mathsf{DEC}[i-1] + 1$, $\mathsf{DEC}[i] = 1$. If $A[i] < A[i-1]$: $\mathsf{DEC}[i] = \mathsf{INC}[i-1] + 1$, $\mathsf{INC}[i] = 1$. If $A[i] = A[i-1]$: $\mathsf{INC}[i] = \mathsf{DEC}[i] = 1$.

An increasing step following a decreasing step (or vice versa) extends the turbulent run; otherwise it resets. Return $\max$ over all $\mathsf{INC}[i]$ and $\mathsf{DEC}[i]$.

ALG(A):
  inc = [1] * n
  dec = [1] * n
  for i = 2, ..., n:
    if A[i] > A[i-1]:
      inc[i] = dec[i-1] + 1
    else if A[i] < A[i-1]:
      dec[i] = inc[i-1] + 1
  return max(max(inc), max(dec))

The algorithm makes $n-1$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 413.) For all $i \in {3, \ldots, n}$, let $\mathsf{OPT}[i]$ denote the number of arithmetic slices ending at $A[i]$. If $A[i] - A[i-1] = A[i-1] - A[i-2]$, then $\mathsf{OPT}[i] = \mathsf{OPT}[i-1] + 1$ (the previous slices each extend by one element, plus one new slice of length $3$). Otherwise $\mathsf{OPT}[i] = 0$. We return $\sum \mathsf{OPT}[i]$.

ALG(A):
  d = [0] * n
  for i = 3, ..., n:
    if A[i] - A[i-1] = A[i-1] - A[i-2]:
      d[i] = d[i-1] + 1
  return sum(d)

The algorithm makes $n-2$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 55.) For all $i \in {1, \ldots, n}$, let $\mathsf{OPT}[i]$ be true if index $i$ is reachable. The base case is $\mathsf{OPT}[1] = \text{true}$. The recurrence is:

$$\mathsf{OPT}[i] = \bigvee_{j=1}^{i-1} \bigl(\mathsf{OPT}[j] \text{ and } j + A[j] \geq i\bigr).$$

Index $i$ is reachable if and only if some earlier reachable index $j$ can jump far enough. We return $\mathsf{OPT}[n]$.

ALG(A):
  d = [false] * n
  d[1] = true
  for i = 2, ..., n:
    for j = 1, ..., i-1:
      if d[j] and j + A[j] >= i:
        d[i] = true
        break
  return d[n]

There are $n$ subproblems each scanning up to $n$ previous entries, so the total running time is $O(n^2)$.

(This is LeetCode 45.) For all $i \in {1, \ldots, n}$, let $\mathsf{OPT}[i]$ denote the minimum number of jumps from index $1$ to index $i$. The base case is $\mathsf{OPT}[1] = 0$. The recurrence is:

$$\mathsf{OPT}[i] = 1 + \min_{j < i,; j + A[j] \geq i} \mathsf{OPT}[j].$$

To reach $i$, we must jump from some reachable $j$ where $j + A[j] \geq i$; we pick the $j$ with fewest jumps.

ALG(A):
  d = [inf] * n
  d[1] = 0
  for i = 2, ..., n:
    for j = 1, ..., i-1:
      if j + A[j] >= i:
        d[i] = min(d[i], d[j] + 1)
  return d[n]

There are $n$ subproblems each taking $O(n)$ time, so the total running time is $O(n^2)$.

(This is LeetCode 213.) Since $A[1]$ and $A[n]$ are adjacent, we cannot pick both. Run the linear house-robber algorithm (Problem 4.6) twice: once on $A[1 ,:, n-1]$ (excluding the last) and once on $A[2 ,:, n]$ (excluding the first). Return the larger of the two results.

If $n = 1$, return $A[1]$. Otherwise, define $\text{rob}(L, R)$ as the standard non-adjacent max sum on $A[L ,:, R]$ from Problem 4.6.

ALG(A):
  if n = 1: return A[1]
  return max(rob(1, n-1), rob(2, n))

rob(L, R):
  if R - L = 0: return A[L]
  prev2 = A[L]
  prev1 = max(A[L], A[L+1])
  for i = L+2, ..., R:
    curr = max(prev1, A[i] + prev2)
    prev2 = prev1
    prev1 = curr
  return prev1

Each call to $\text{rob}$ takes $O(n)$ time, so the total running time is $O(n)$.

(This is LeetCode 740.) Build a frequency-weighted array $C$ of length $M$ where $C[v] = v \cdot \text{count}(v)$. Picking value $v$ earns $C[v]$ and forbids $v-1$ and $v+1$, so this reduces to the house-robber problem (Problem 4.6) on $C$.

ALG(A):
  M = max(A)
  C = [0] * (M+1)
  for x in A:
    C[x] += x
  if M = 1: return C[1]
  prev2 = C[1]
  prev1 = max(C[1], C[2])
  for v = 3, ..., M:
    curr = max(prev1, C[v] + prev2)
    prev2 = prev1
    prev1 = curr
  return prev1

Building $C$ takes $O(n)$. The loop over values takes $O(M)$. Total running time: $O(n + M)$.

(This is LeetCode 91.) For all $i \in {1, \ldots, n}$, let $\mathsf{OPT}[i]$ denote the number of decodings of $A[1 ,:, i]$. Set $\mathsf{OPT}[0] = 1$ (empty prefix has one decoding). The recurrence is:

$$\mathsf{OPT}[i] = [A[i] \geq 1] \cdot \mathsf{OPT}[i-1] ;+; [10 \leq 10 A[i-1] + A[i] \leq 26] \cdot \mathsf{OPT}[i-2]$$

where $[\cdot]$ is $1$ if the condition holds and $0$ otherwise. We can decode $A[i]$ alone if it is nonzero, and we can decode $A[i-1..i]$ as a pair if it forms a number between $10$ and $26$.

ALG(A):
  d = [0] * (n+1)
  d[0] = 1
  for i = 1, ..., n:
    if A[i] >= 1:
      d[i] += d[i-1]
    if i >= 2 and 10 <= 10*A[i-1] + A[i] <= 26:
      d[i] += d[i-2]
  return d[n]

The algorithm makes $n$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 42.) The water above bar $i$ is $\max(0,; \min(L[i], R[i]) - A[i])$, where $L[i] = \max(A[1], \ldots, A[i])$ and $R[i] = \max(A[i], \ldots, A[n])$. We compute $L$ and $R$ in two passes:

ALG(A):
  L = [0] * n
  R = [0] * n
  L[1] = A[1]
  for i = 2, ..., n:
    L[i] = max(L[i-1], A[i])
  R[n] = A[n]
  for i = n-1, ..., 1:
    R[i] = max(R[i+1], A[i])
  water = 0
  for i = 1, ..., n:
    water += max(0, min(L[i], R[i]) - A[i])
  return water

The left-max array ensures $L[i]$ is the tallest bar to the left (including $i$), and similarly for $R[i]$. The water at each position is bounded by the shorter of the two tallest walls minus the bar’s own height. Each of the three passes takes $O(n)$ time, so the total running time is $O(n)$.

(This is LeetCode 983.) For all $i \in {1, \ldots, m}$, let $\mathsf{OPT}[i]$ denote the minimum cost to cover travel days $D[1], \ldots, D[i]$. Set $\mathsf{OPT}[0] = 0$. The recurrence is:

$$\mathsf{OPT}[i] = \min\bigl(C[1] + \mathsf{OPT}[i-1],; C[2] + \mathsf{OPT}[j_7],; C[3] + \mathsf{OPT}[j_{30}]\bigr)$$

where $j_7$ is the largest $j$ such that $D[j] < D[i] - 6$ (or $0$ if none) and $j_{30}$ is the largest $j$ such that $D[j] < D[i] - 29$. We buy a pass covering day $D[i]$ and all travel days within its window.

ALG(D, C):
  d = [0] * (m+1)
  for i = 1, ..., m:
    d[i] = C[1] + d[i-1]
    j = i - 1
    while j >= 1 and D[j] >= D[i] - 6: j -= 1
    d[i] = min(d[i], C[2] + d[j])
    while j >= 1 and D[j] >= D[i] - 29: j -= 1
    d[i] = min(d[i], C[3] + d[j])
  return d[m]

Each pointer $j$ only moves left, so the total work across all iterations is $O(m)$.

(This is LeetCode 276.) Let $\mathsf{S}[i]$ = number of colorings where post $i$ has the same color as post $i-1$, and $\mathsf{D}[i]$ = number where they differ. Base cases: $\mathsf{S}[2] = k$ (posts $1$ and $2$ same color, $k$ choices), $\mathsf{D}[2] = k(k-1)$. Recurrences:

$$\mathsf{S}[i] = \mathsf{D}[i-1], \qquad \mathsf{D}[i] = (k-1)(\mathsf{S}[i-1] + \mathsf{D}[i-1]).$$

We can only paint post $i$ the same as $i-1$ if $i-1$ differs from $i-2$ (otherwise three consecutive would match). We return $\mathsf{S}[n] + \mathsf{D}[n]$.

ALG(n, k):
  if n = 1: return k
  s, d = k, k*(k-1)
  for i = 3, ..., n:
    s, d = d, (k-1)*(s + d)
  return s + d

The algorithm makes $n-2$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 1014.) Rewrite the score as $(A[i] + i) + (A[j] - j)$. For each $j$, we want the largest $A[i] + i$ among all $i < j$. Track this running maximum as $j$ increases.

ALG(A):
  best = -inf
  maxLeft = A[1] + 1
  for j = 2, ..., n:
    best = max(best, maxLeft + A[j] - j)
    maxLeft = max(maxLeft, A[j] + j)
  return best

At each step, $\text{maxLeft}$ holds $\max_{i \leq j}(A[i]+i)$, so the pairing with $A[j]-j$ gives the best score using $j$ as the right endpoint. The algorithm makes $n-1$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 1043.) For all $i \in {1, \ldots, n}$, let $\mathsf{OPT}[i]$ denote the maximum sum for $A[1 ,:, i]$. Set $\mathsf{OPT}[0] = 0$. The recurrence tries every last-segment length $\ell$ from $1$ to $k$:

$$\mathsf{OPT}[i] = \max_{\ell = 1}^{\min(i,k)} \bigl(\mathsf{OPT}[i-\ell] + \ell \cdot \max(A[i-\ell+1 ,:, i])\bigr).$$

We pick the last-segment length that maximizes the sum. We can track the running max of the last segment as $\ell$ grows.

ALG(A, k):
  d = [0] * (n+1)
  for i = 1, ..., n:
    curMax = 0
    for L = 1, ..., min(i, k):
      curMax = max(curMax, A[i-L+1])
      d[i] = max(d[i], d[i-L] + L * curMax)
  return d[n]

There are $n$ subproblems, each scanning at most $k$ segment lengths, so the total running time is $O(nk)$.

(This is LeetCode 813.) Precompute prefix sums so that $\text{avg}(A[p+1 ,:, i]) = (S[i] - S[p]) / (i - p)$ in $O(1)$. Let $\mathsf{OPT}[i][j]$ denote the maximum sum of averages for $A[1 ,:, i]$ using exactly $j$ groups. Base case: $\mathsf{OPT}[i][1] = S[i] / i$. Recurrence for $j \geq 2$:

$$\mathsf{OPT}[i][j] = \max_{p = j-1}^{i-1} \bigl(\mathsf{OPT}[p][j-1] + \text{avg}(A[p+1 ,:, i])\bigr).$$

The last group is $A[p+1 ,:, i]$ and the first $j-1$ groups cover $A[1 ,:, p]$. We return $\max_{j=1}^{k} \mathsf{OPT}[n][j]$.

ALG(A, k):
  S = prefix sums of A
  d = 2D array of size (n+1) x (k+1), init to 0
  for i = 1, ..., n:
    d[i][1] = S[i] / i
    for j = 2, ..., min(i, k):
      for p = j-1, ..., i-1:
        d[i][j] = max(d[i][j], d[p][j-1] + (S[i]-S[p])/(i-p))
  return max(d[n][1], ..., d[n][k])

There are $O(nk)$ subproblems, each taking $O(n)$ time, so the total running time is $O(n^2 k)$.

(This is LeetCode 1911.) Maintain two states: $\mathsf{ODD}$ = best alternating sum for a subsequence of odd length (the last picked element is added), and $\mathsf{EVEN}$ = best for even length (the last picked element is subtracted). Initialize $\mathsf{ODD} = 0$ and $\mathsf{EVEN} = 0$. For each $A[i]$:

$$\mathsf{ODD} = \max(\mathsf{ODD},; \mathsf{EVEN} + A[i]), \qquad \mathsf{EVEN} = \max(\mathsf{EVEN},; \mathsf{ODD} - A[i]).$$

We can either skip $A[i]$ or extend the current subsequence. Return $\mathsf{ODD}$.

ALG(A):
  odd, even = 0, 0
  for i = 1, ..., n:
    odd, even = max(odd, even + A[i]), max(even, odd - A[i])
  return odd

The algorithm makes $n$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 1027.) For each index $i$ and common difference $d$, let $\mathsf{OPT}[i][d]$ = length of the longest arithmetic subsequence ending at $A[i]$ with difference $d$. For each pair $j < i$, set $d = A[i] - A[j]$ and $\mathsf{OPT}[i][d] = \mathsf{OPT}[j][d] + 1$ (default $\mathsf{OPT}[j][d] = 1$). Use a hash map at each index for the $d$ dimension.

ALG(A):
  dp = array of n hash maps, each empty
  best = 2
  for i = 1, ..., n:
    for j = 1, ..., i-1:
      d = A[i] - A[j]
      prev = dp[j].get(d, 1)
      dp[i][d] = max(dp[i].get(d, 1), prev + 1)
      best = max(best, dp[i][d])
  return best

There are $O(n^2)$ pairs $(j, i)$, each processed in $O(1)$ time with hash maps, so the total running time is $O(n^2)$.

(This is LeetCode 1218.) Let $\mathsf{OPT}[v]$ denote the length of the longest valid subsequence ending with value $v$. Use a hash map. For each $A[i]$, $\mathsf{OPT}[A[i]] = \mathsf{OPT}[A[i] - d] + 1$ (default $0$ if key not found). Return $\max(\mathsf{OPT})$.

The preceding element in the subsequence has value $A[i] - d$; the hash map gives us the best length ending with that value in $O(1)$.

ALG(A, d):
  dp = empty hash map
  for i = 1, ..., n:
    dp[A[i]] = dp.get(A[i] - d, 0) + 1
  return max value in dp

The algorithm makes $n$ iterations each taking $O(1)$ expected time, so the total running time is $O(n)$.

(This is LeetCode 1031.) Precompute prefix sums $S$ so that $\text{sum}(A[i ,:, j]) = S[j] - S[i-1]$ in $O(1)$. For each split point $i$, the $L$-length subarray is to the left and the $M$-length subarray is to the right (or vice versa). Track the running best $L$-length sum as we scan.

ALG(A, L, M):
  S = prefix sums of A
  bestL = S[L]                # best L-subarray in A[1..L]
  bestM = S[M]                # best M-subarray in A[1..M]
  ans = -inf
  # Case 1: L-subarray before M-subarray
  for i = L+M, ..., n:
    bestL = max(bestL, S[i-M] - S[i-M-L])
    ans = max(ans, bestL + S[i] - S[i-M])
  # Case 2: M-subarray before L-subarray
  for i = L+M, ..., n:
    bestM = max(bestM, S[i-L] - S[i-L-M])
    ans = max(ans, bestM + S[i] - S[i-L])
  return ans

Each of the two passes takes $O(n)$ time, so the total running time is $O(n)$.

(This is LeetCode 801.) For each index $i$, define two states: $\mathsf{KEEP}[i]$ = min swaps to make the first $i$ positions increasing if we do not swap at $i$, and $\mathsf{SWAP}[i]$ = min swaps if we do swap at $i$. Initialize $\mathsf{KEEP}[1] = 0$, $\mathsf{SWAP}[1] = 1$.

For $i \geq 2$: if the natural order works ($A[i] > A[i-1]$ and $B[i] > B[i-1]$), we can keep both or swap both. If the crossed order works ($A[i] > B[i-1]$ and $B[i] > A[i-1]$), we can keep one and swap the other.

ALG(A, B):
  keep, swap = 0, 1
  for i = 2, ..., n:
    newKeep, newSwap = inf, inf
    if A[i] > A[i-1] and B[i] > B[i-1]:
      newKeep = min(newKeep, keep)
      newSwap = min(newSwap, swap + 1)
    if A[i] > B[i-1] and B[i] > A[i-1]:
      newKeep = min(newKeep, swap)
      newSwap = min(newSwap, keep + 1)
    keep, swap = newKeep, newSwap
  return min(keep, swap)

The algorithm makes $n-1$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 873.) Build a hash map $\text{idx}$ mapping each value to its index. For each pair $(j, i)$ with $j < i$, let $\mathsf{OPT}[j][i]$ denote the length of the longest Fibonacci subsequence ending with $(A[j], A[i])$. Look up $A[i] - A[j]$ in the hash map; if it maps to some $k < j$, then $\mathsf{OPT}[j][i] = \mathsf{OPT}[k][j] + 1$. Otherwise $\mathsf{OPT}[j][i] = 2$.

ALG(A):
  idx = hash map: A[i] -> i for all i
  best = 0
  dp = 2D array of size n x n, init all to 2
  for i = 1, ..., n:
    for j = 1, ..., i-1:
      target = A[i] - A[j]
      if target < A[j] and target in idx:
        k = idx[target]
        dp[j][i] = dp[k][j] + 1
        best = max(best, dp[j][i])
  return best if best >= 3 else 0

There are $O(n^2)$ pairs, each processed in $O(1)$ time with the hash map, so the total running time is $O(n^2)$.

(This is LeetCode 322.) For all $i \in {0, 1, \ldots, n}$, let $\mathsf{OPT}[i]$ denote the minimum coins to make $i$. Base case: $\mathsf{OPT}[0] = 0$. Recurrence:

$$\mathsf{OPT}[i] = 1 + \min_{j : C[j] \leq i} \mathsf{OPT}[i - C[j]].$$

The last coin used has some denomination $C[j]$; we try all denominations and pick the best.

ALG(C, n):
  d = [inf] * (n+1)
  d[0] = 0
  for i = 1, ..., n:
    for j = 1, ..., k:
      if C[j] <= i:
        d[i] = min(d[i], d[i - C[j]] + 1)
  return d[n] if d[n] < inf else -1

There are $n+1$ subproblems, each checking $k$ coins, so the total running time is $O(nk)$.

(This is LeetCode 518.) Let $\mathsf{OPT}[j][i]$ = number of ways to make $i$ using only coins $C[1], \ldots, C[j]$. Base case: $\mathsf{OPT}[0][0] = 1$, $\mathsf{OPT}[0][i] = 0$ for $i > 0$. Recurrence:

$$\mathsf{OPT}[j][i] = \mathsf{OPT}[j-1][i] + \begin{cases} \mathsf{OPT}[j][i - C[j]] & \text{if } C[j] \leq i \ 0 & \text{otherwise.} \end{cases}$$

Either we don’t use coin $j$ (first term), or we use it at least once (second term — note $\mathsf{OPT}[j]$, not $\mathsf{OPT}[j-1]$, because we can reuse coin $j$). We can reduce to 1D:

ALG(C, n):
  d = [0] * (n+1)
  d[0] = 1
  for j = 1, ..., k:
    for i = C[j], ..., n:
      d[i] += d[i - C[j]]
  return d[n]

By iterating coins in the outer loop, each combination is counted exactly once (avoiding order duplicates). The total running time is $O(nk)$.

(This is LeetCode 377.) For all $i \in {0, \ldots, n}$, let $\mathsf{OPT}[i]$ = number of ordered sequences summing to $i$. Base case: $\mathsf{OPT}[0] = 1$. Recurrence:

$$\mathsf{OPT}[i] = \sum_{j=1}^{k} [,C[j] \leq i,] \cdot \mathsf{OPT}[i - C[j]].$$

The last element in the sequence is some $C[j]$; we sum over all valid choices. Unlike Coin Change II, order matters here, so we iterate amounts in the outer loop.

ALG(C, n):
  d = [0] * (n+1)
  d[0] = 1
  for i = 1, ..., n:
    for j = 1, ..., k:
      if C[j] <= i:
        d[i] += d[i - C[j]]
  return d[n]

There are $n+1$ subproblems each scanning $k$ coins, so the total running time is $O(nk)$.

(This is LeetCode 279.) For all $i \in {0, \ldots, n}$, let $\mathsf{OPT}[i]$ = minimum perfect squares summing to $i$. Base case: $\mathsf{OPT}[0] = 0$. Recurrence:

$$\mathsf{OPT}[i] = 1 + \min_{j^2 \leq i} \mathsf{OPT}[i - j^2].$$

The last square used is $j^2$; we try all $j$ from $1$ to $\lfloor\sqrt{i}\rfloor$.

ALG(n):
  d = [inf] * (n+1)
  d[0] = 0
  for i = 1, ..., n:
    for j = 1, 2, ..., while j*j <= i:
      d[i] = min(d[i], d[i - j*j] + 1)
  return d[n]

For each $i$, we try $O(\sqrt{i})$ squares. The total running time is $\sum_{i=1}^{n} O(\sqrt{i}) = O(n\sqrt{n})$.

(This is LeetCode 343.) For all $i \in {2, \ldots, n}$, let $\mathsf{OPT}[i]$ = maximum product from breaking $i$. Set $\mathsf{OPT}[1] = 1$. Recurrence:

$$\mathsf{OPT}[i] = \max_{j=1}^{i-1} j \cdot \max(i - j,; \mathsf{OPT}[i-j]).$$

We split off $j$ and either keep $i-j$ as a single piece or break it further. For $i - j$, we take the better of not breaking ($i-j$ itself) and breaking ($\mathsf{OPT}[i-j]$).

ALG(n):
  d = [0] * (n+1)
  d[1] = 1
  for i = 2, ..., n:
    for j = 1, ..., i-1:
      d[i] = max(d[i], j * max(i-j, d[i-j]))
  return d[n]

There are $n$ subproblems each taking $O(n)$ time, so the total running time is $O(n^2)$.

(This is LeetCode 96.) Let $\mathsf{OPT}[i]$ = number of structurally unique BSTs with $i$ nodes. Base case: $\mathsf{OPT}[0] = 1$, $\mathsf{OPT}[1] = 1$. Recurrence (Catalan numbers):

$$\mathsf{OPT}[i] = \sum_{r=1}^{i} \mathsf{OPT}[r-1] \cdot \mathsf{OPT}[i-r].$$

If node $r$ is the root, the left subtree has $r-1$ nodes and the right subtree has $i-r$ nodes. The number of BSTs is the product (independent choices).

ALG(n):
  d = [0] * (n+1)
  d[0] = 1
  for i = 1, ..., n:
    for r = 1, ..., i:
      d[i] += d[r-1] * d[i-r]
  return d[n]

There are $n+1$ subproblems, and computing $\mathsf{OPT}[i]$ takes $O(i)$ time. Total: $\sum_{i=1}^{n} O(i) = O(n^2)$.

(This is LeetCode 1155.) Let $\mathsf{OPT}[i][s]$ = number of ways to roll $i$ dice to get sum $s$. Base case: $\mathsf{OPT}[0][0] = 1$. Recurrence:

$$\mathsf{OPT}[i][s] = \sum_{v=1}^{f} \mathsf{OPT}[i-1][s-v]$$

(where $\mathsf{OPT}[i-1][s-v] = 0$ if $s - v < 0$). Die $i$ shows face $v$, and the remaining $i-1$ dice sum to $s-v$. Return $\mathsf{OPT}[d][t]$.

ALG(d, f, t):
  dp = 2D array (d+1) x (t+1), init to 0
  dp[0][0] = 1
  for i = 1, ..., d:
    for s = i, ..., t:
      for v = 1, ..., f:
        if s - v >= 0:
          dp[i][s] += dp[i-1][s-v]
  return dp[d][t]

There are $d \cdot t$ subproblems, each checking $f$ faces, so the total running time is $O(dft)$.

(This is LeetCode 338.) For all $i \in {1, \ldots, n}$, the recurrence is:

$$B[i] = B[i \gg 1] + (i \bmod 2)$$

where $i \gg 1$ is $\lfloor i/2 \rfloor$ (right shift). Removing the last bit of $i$ gives $\lfloor i/2 \rfloor$, and the last bit contributes $i \bmod 2$.

ALG(n):
  B = [0] * (n+1)
  for i = 1, ..., n:
    B[i] = B[i / 2] + (i mod 2)
  return B

The algorithm makes $n$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 264.) Let $U[i]$ = the $i$-th ugly number. Base case: $U[1] = 1$. Maintain three pointers $p_2, p_3, p_5$, all starting at $1$. At each step:

$$U[i] = \min(2 \cdot U[p_2],; 3 \cdot U[p_3],; 5 \cdot U[p_5]).$$

Advance whichever pointer(s) produced the minimum. Every ugly number is $2$, $3$, or $5$ times a smaller ugly number, and the pointers ensure we generate them in order.

ALG(n):
  U = [0] * (n+1)
  U[1] = 1
  p2, p3, p5 = 1, 1, 1
  for i = 2, ..., n:
    U[i] = min(2*U[p2], 3*U[p3], 5*U[p5])
    if U[i] = 2*U[p2]: p2 += 1
    if U[i] = 3*U[p3]: p3 += 1
    if U[i] = 5*U[p5]: p5 += 1
  return U[n]

The algorithm makes $n-1$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 790.) Let $\mathsf{OPT}[i]$ = number of ways to tile a $2 \times i$ board. After accounting for how dominoes and trominoes can fill the last columns, the recurrence is:

$$\mathsf{OPT}[i] = 2 \cdot \mathsf{OPT}[i-1] + \mathsf{OPT}[i-3]$$

with base cases $\mathsf{OPT}[1] = 1$, $\mathsf{OPT}[2] = 2$, $\mathsf{OPT}[3] = 5$. The $2 \cdot \mathsf{OPT}[i-1]$ accounts for one vertical domino or two tromino extensions, and $\mathsf{OPT}[i-3]$ accounts for the two L-tromino placements that span three columns.

ALG(n):
  if n <= 2: return n
  d = [0] * (n+1)
  d[1], d[2], d[3] = 1, 2, 5
  for i = 4, ..., n:
    d[i] = 2*d[i-1] + d[i-3]
  return d[n]

The algorithm makes $n - 3$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 935.) Let $\mathsf{OPT}[i][d]$ = number of $i$-digit numbers ending on digit $d$. Base case: $\mathsf{OPT}[1][d] = 1$ for all $d$. The knight’s moves define a fixed adjacency: from $1 \to {6,8}$, $2 \to {7,9}$, $3 \to {4,8}$, $4 \to {3,9,0}$, $5 \to {}$, $6 \to {1,7,0}$, $7 \to {2,6}$, $8 \to {1,3}$, $9 \to {2,4}$, $0 \to {4,6}$.

$$\mathsf{OPT}[i][d] = \sum_{d’ \in \text{jumps}(d)} \mathsf{OPT}[i-1][d’].$$

Return $\sum_{d=0}^{9} \mathsf{OPT}[n][d]$.

ALG(n):
  jumps = adjacency list as above
  dp = [1] * 10
  for i = 2, ..., n:
    new_dp = [0] * 10
    for d = 0, ..., 9:
      for d' in jumps[d]:
        new_dp[d] += dp[d']
    dp = new_dp
  return sum(dp)

Each iteration does $O(10)$ work (constant), so the total running time is $O(n)$.

(This is LeetCode 1641.) Let $\mathsf{OPT}[i][v]$ = number of sorted strings of length $i$ ending with the $v$-th vowel ($v = 1, \ldots, 5$). Base case: $\mathsf{OPT}[1][v] = 1$. Recurrence: the $v$-th vowel can follow any vowel $\leq v$, so:

$$\mathsf{OPT}[i][v] = \sum_{u=1}^{v} \mathsf{OPT}[i-1][u].$$

Return $\sum_{v=1}^{5} \mathsf{OPT}[n][v]$. We can optimize using prefix sums.

ALG(n):
  dp = [1, 1, 1, 1, 1]
  for i = 2, ..., n:
    for v = 2, ..., 5:
      dp[v] += dp[v-1]
  return sum(dp)

Each iteration does $O(5) = O(1)$ work, so the total running time is $O(n)$.

(This is LeetCode 1137.) Same idea as Fibonacci (Problem 4.1): compute iteratively.

ALG(n):
  if n = 0: return 0
  if n <= 2: return 1
  a, b, c = 0, 1, 1
  for i = 3, ..., n:
    a, b, c = b, c, a + b + c
  return c

The algorithm makes $n-2$ iterations each taking $O(1)$ time, so the total running time is $O(n)$. Space is $O(1)$.

(This is LeetCode 256.) Let $\mathsf{OPT}[i][j]$ = min cost to paint houses $1, \ldots, i$ where house $i$ has color $j$. Base case: $\mathsf{OPT}[1][j] = C[1][j]$. Recurrence:

$$\mathsf{OPT}[i][j] = C[i][j] + \min_{j’ \neq j} \mathsf{OPT}[i-1][j’].$$

Since there are only $3$ colors, the $\min$ over the other two colors takes $O(1)$. Return $\min_j \mathsf{OPT}[n][j]$.

ALG(C):
  dp = [C[1][1], C[1][2], C[1][3]]
  for i = 2, ..., n:
    dp = [C[i][1] + min(dp[2], dp[3]),
          C[i][2] + min(dp[1], dp[3]),
          C[i][3] + min(dp[1], dp[2])]
  return min(dp)

The algorithm makes $n-1$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 265.) Same recurrence as Paint House: $\mathsf{OPT}[i][j] = C[i][j] + \min_{j’ \neq j} \mathsf{OPT}[i-1][j’]$. The key optimization: for each row, precompute the smallest and second-smallest values. When $j$ is the color achieving the min, use the second-smallest; otherwise use the smallest. This makes the $\min_{j’ \neq j}$ step $O(1)$ per color.

ALG(C):
  dp = C[1]
  for i = 2, ..., n:
    m1, m2 = smallest and 2nd smallest of dp
    idx1 = index achieving m1
    new_dp = [0] * k
    for j = 1, ..., k:
      if j = idx1:
        new_dp[j] = C[i][j] + m2
      else:
        new_dp[j] = C[i][j] + m1
    dp = new_dp
  return min(dp)

Finding the two smallest takes $O(k)$; the inner loop is $O(k)$. Over $n$ rows, the total running time is $O(nk)$.

Let $\mathsf{OPT}[i][s]$ = true if some subset of $A[1 ,:, i]$ sums to $s$. Base cases: $\mathsf{OPT}[0][0] = \text{true}$, $\mathsf{OPT}[0][s] = \text{false}$ for $s > 0$. Recurrence:

$$\mathsf{OPT}[i][s] = \mathsf{OPT}[i-1][s] ;\lor; (A[i] \leq s \text{ and } \mathsf{OPT}[i-1][s - A[i]]).$$

Either we exclude $A[i]$ or include it. We reduce to 1D by iterating $s$ in decreasing order:

ALG(A, T):
  d = [false] * (T+1)
  d[0] = true
  for i = 1, ..., n:
    for s = T, ..., A[i]:
      d[s] = d[s] or d[s - A[i]]
  return d[T]

There are $n \cdot T$ state transitions, so the total running time is $O(nT)$.

(This is LeetCode 416.) If $S$ is odd, return false. Otherwise, reduce to subset sum with target $T = S/2$: can we find a subset summing to $T$? Apply the algorithm from Problem 4.48.

ALG(A):
  S = sum(A)
  if S is odd: return false
  T = S / 2
  d = [false] * (T+1)
  d[0] = true
  for i = 1, ..., n:
    for s = T, ..., A[i]:
      d[s] = d[s] or d[s - A[i]]
  return d[T]

The total running time is $O(nT) = O(nS)$.

(This is LeetCode 494.) Let the positive subset sum be $P$ and negative subset sum be $N$. Then $P - N = T$ and $P + N = S$, so $P = (S + T)/2$. If $S + T$ is odd or $|T| > S$, return $0$. Otherwise, count subsets of $A$ summing to $P$.

ALG(A, T):
  S = sum(A)
  if (S + T) is odd or |T| > S: return 0
  P = (S + T) / 2
  d = [0] * (P+1)
  d[0] = 1
  for i = 1, ..., n:
    for s = P, ..., A[i]:
      d[s] += d[s - A[i]]
  return d[P]

The total running time is $O(nP) = O(nS)$.

(This is LeetCode 1049.) The problem is equivalent to partitioning $A$ into two groups and minimizing the absolute difference of their sums. If one group sums to $s$, the other sums to $S - s$, and the difference is $|S - 2s|$. We want the largest $s \leq S/2$ achievable. This is a subset-sum problem.

ALG(A):
  S = sum(A)
  T = S / 2  # integer division
  d = [false] * (T+1)
  d[0] = true
  for i = 1, ..., n:
    for s = T, ..., A[i]:
      d[s] = d[s] or d[s - A[i]]
  for s = T, ..., 0:
    if d[s]: return S - 2*s

The total running time is $O(nT) = O(nS)$.

Let $\mathsf{OPT}[i][j]$ = max value using items $1, \ldots, i$ with capacity $j$. Base case: $\mathsf{OPT}[0][j] = 0$. Recurrence:

$$\mathsf{OPT}[i][j] = \begin{cases} \mathsf{OPT}[i-1][j] & \text{if } w_i > j \ \max(\mathsf{OPT}[i-1][j],; v_i + \mathsf{OPT}[i-1][j - w_i]) & \text{otherwise.} \end{cases}$$

Skip item $i$ or take it (if it fits). By induction, each subproblem is correct. Return $\mathsf{OPT}[n][W]$.

ALG(w, v, W):
  dp = 2D array (n+1) x (W+1), init to 0
  for i = 1, ..., n:
    for j = 0, ..., W:
      dp[i][j] = dp[i-1][j]
      if w[i] <= j:
        dp[i][j] = max(dp[i][j], v[i] + dp[i-1][j - w[i]])
  return dp[n][W]

The table has $(n+1)(W+1)$ entries, each computed in $O(1)$. Total: $O(nW)$.

Let $\mathsf{OPT}[j]$ = max value achievable with capacity $j$. Base case: $\mathsf{OPT}[0] = 0$. Recurrence:

$$\mathsf{OPT}[j] = \max_{i : w_i \leq j} (v_i + \mathsf{OPT}[j - w_i]).$$

Since items are reusable, we reference $\mathsf{OPT}[j - w_i]$ (same row, not previous).

ALG(w, v, W):
  d = [0] * (W+1)
  for j = 1, ..., W:
    for i = 1, ..., n:
      if w[i] <= j:
        d[j] = max(d[j], v[i] + d[j - w[i]])
  return d[W]

There are $W+1$ subproblems, each checking $n$ items, so the total running time is $O(nW)$.

(This is LeetCode 474.) This is a 2D knapsack. Let $\mathsf{OPT}[m][p]$ = max pairs selectable with $m$ zeros and $p$ ones remaining. Process items in 0/1 fashion (iterate capacities in decreasing order):

ALG(pairs, M, N):
  dp = 2D array (M+1) x (N+1), init to 0
  for i = 1, ..., n:
    (a, b) = pairs[i]
    for m = M, ..., a:
      for p = N, ..., b:
        dp[m][p] = max(dp[m][p], dp[m-a][p-b] + 1)
  return dp[M][N]

For each item, we update $O(MN)$ cells. Total: $O(nMN)$.

(This is LeetCode 1262.) Let $\mathsf{OPT}[r]$ = max sum achievable with sum $\equiv r \pmod{3}$, for $r \in {0, 1, 2}$. Initialize $\mathsf{OPT}[0] = 0$, $\mathsf{OPT}[1] = \mathsf{OPT}[2] = -\infty$. For each $A[i]$, update all three remainders:

$$\mathsf{OPT}’[r] = \max(\mathsf{OPT}[r],; A[i] + \mathsf{OPT}[(r - A[i]) \bmod 3])$$

Return $\mathsf{OPT}[0]$.

ALG(A):
  dp = [0, -inf, -inf]
  for i = 1, ..., n:
    old = copy of dp
    for r = 0, 1, 2:
      dp[(old[r] + A[i]) mod 3] = max(dp[(old[r] + A[i]) mod 3], old[r] + A[i])
  return dp[0]

Each iteration does $O(1)$ work (only $3$ remainders), so the total running time is $O(n)$.

(This is LeetCode 1269.) Let $\mathsf{OPT}[t][i]$ = number of ways to be at index $i$ after $t$ steps. Base case: $\mathsf{OPT}[0][0] = 1$. Recurrence:

$$\mathsf{OPT}[t][i] = \mathsf{OPT}[t-1][i] + \mathsf{OPT}[t-1][i-1] + \mathsf{OPT}[t-1][i+1]$$

(treating out-of-bound indices as $0$). We only need indices up to $\min(\text{steps}/2, n-1)$ since the pointer can’t go farther than $\text{steps}/2$ and return. Return $\mathsf{OPT}[\text{steps}][0]$.

ALG(steps, n):
  maxPos = min(steps / 2, n - 1)
  dp = [0] * (maxPos + 1)
  dp[0] = 1
  for t = 1, ..., steps:
    new_dp = [0] * (maxPos + 1)
    for i = 0, ..., maxPos:
      new_dp[i] = dp[i]
      if i > 0: new_dp[i] += dp[i-1]
      if i < maxPos: new_dp[i] += dp[i+1]
    dp = new_dp
  return dp[0]

Each step processes $O(\min(\text{steps}, n))$ positions, so the total running time is $O(\text{steps} \cdot \min(\text{steps}, n))$.

(This is LeetCode 1105.) For all $i \in {1, \ldots, n}$, let $\mathsf{OPT}[i]$ = min total height for books $1, \ldots, i$. Set $\mathsf{OPT}[0] = 0$. The recurrence tries placing books $j+1, \ldots, i$ on the last shelf:

$$\mathsf{OPT}[i] = \min_{j} \bigl(\mathsf{OPT}[j] + \max(h_{j+1}, \ldots, h_i)\bigr) \quad \text{where } \sum_{k=j+1}^{i} t_k \leq W.$$

ALG(books, W):
  d = [inf] * (n+1)
  d[0] = 0
  for i = 1, ..., n:
    width, height = 0, 0
    for j = i, ..., 1:
      width += t[j]
      if width > W: break
      height = max(height, h[j])
      d[i] = min(d[i], d[j-1] + height)
  return d[n]

For each $i$, the inner loop runs while $\text{width} \leq W$, which is at most $W$ iterations (since each $t_j \geq 1$). Total: $O(nW)$.

(This is LeetCode 64.) Let $\mathsf{OPT}[i][j]$ = min sum to reach cell $(i,j)$. Base case: $\mathsf{OPT}[1][1] = G[1][1]$. Recurrence:

$$\mathsf{OPT}[i][j] = G[i][j] + \min(\mathsf{OPT}[i-1][j],; \mathsf{OPT}[i][j-1])$$

(treating out-of-bound entries as $\infty$). We can only arrive from above or left. Return $\mathsf{OPT}[m][n]$.

ALG(G):
  dp = m x n array
  dp[1][1] = G[1][1]
  for j = 2, ..., n: dp[1][j] = dp[1][j-1] + G[1][j]
  for i = 2, ..., m: dp[i][1] = dp[i-1][1] + G[i][1]
  for i = 2, ..., m:
    for j = 2, ..., n:
      dp[i][j] = G[i][j] + min(dp[i-1][j], dp[i][j-1])
  return dp[m][n]

The table has $mn$ entries each computed in $O(1)$, so the total running time is $O(mn)$.

(This is LeetCode 62.) Let $\mathsf{OPT}[i][j]$ = number of paths from $(1,1)$ to $(i,j)$. Base case: $\mathsf{OPT}[1][j] = 1$ for all $j$, $\mathsf{OPT}[i][1] = 1$ for all $i$. Recurrence:

$$\mathsf{OPT}[i][j] = \mathsf{OPT}[i-1][j] + \mathsf{OPT}[i][j-1].$$

Every path to $(i,j)$ comes from above or left. Return $\mathsf{OPT}[m][n]$.

ALG(m, n):
  dp = m x n array, init all to 1
  for i = 2, ..., m:
    for j = 2, ..., n:
      dp[i][j] = dp[i-1][j] + dp[i][j-1]
  return dp[m][n]

The table has $mn$ entries each computed in $O(1)$, so the total running time is $O(mn)$.

(This is LeetCode 120.) Let $\mathsf{OPT}[i][j]$ = min path sum to reach entry $T[i][j]$. Base case: $\mathsf{OPT}[1][1] = T[1][1]$. Recurrence:

$$\mathsf{OPT}[i][j] = T[i][j] + \min(\mathsf{OPT}[i-1][j-1],; \mathsf{OPT}[i-1][j])$$

(treating out-of-bound entries as $\infty$). Return $\min_j \mathsf{OPT}[n][j]$. Alternatively, work bottom-up:

ALG(T):
  d = copy of T[n]  # last row
  for i = n-1, ..., 1:
    for j = 1, ..., i:
      d[j] = T[i][j] + min(d[j], d[j+1])
  return d[1]

The total number of entries is $1 + 2 + \cdots + n = O(n^2)$, each computed in $O(1)$. Total: $O(n^2)$.

(This is LeetCode 931.) Let $\mathsf{OPT}[i][j]$ = min falling path sum ending at $(i,j)$. Base case: $\mathsf{OPT}[1][j] = A[1][j]$. Recurrence:

$$\mathsf{OPT}[i][j] = A[i][j] + \min(\mathsf{OPT}[i-1][j-1],; \mathsf{OPT}[i-1][j],; \mathsf{OPT}[i-1][j+1])$$

(ignoring out-of-bound indices). Return $\min_j \mathsf{OPT}[n][j]$.

ALG(A):
  dp = copy of A
  for i = 2, ..., n:
    for j = 1, ..., n:
      dp[i][j] = A[i][j] + min over valid neighbors dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]
  return min(dp[n])

The table has $n^2$ entries each computed in $O(1)$, so the total running time is $O(n^2)$.

(This is LeetCode 1289.) Same recurrence as Paint House II (Problem 4.47): $\mathsf{OPT}[i][j] = A[i][j] + \min_{j’ \neq j} \mathsf{OPT}[i-1][j’]$. Track the two smallest values in the previous row to compute the $\min$ in $O(1)$.

ALG(A):
  dp = copy of A[1]
  for i = 2, ..., n:
    m1, m2 = smallest and 2nd smallest of dp
    idx1 = index achieving m1
    new_dp = [0] * n
    for j = 1, ..., n:
      if j = idx1:
        new_dp[j] = A[i][j] + m2
      else:
        new_dp[j] = A[i][j] + m1
    dp = new_dp
  return min(dp)

Each row takes $O(n)$ to process. Total: $O(n^2)$.

(This is LeetCode 221.) Let $\mathsf{OPT}[i][j]$ = side length of the largest all-ones square with bottom-right corner at $(i,j)$. Base case: $\mathsf{OPT}[i][j] = M[i][j]$ for first row/column. Recurrence (when $M[i][j] = 1$):

$$\mathsf{OPT}[i][j] = 1 + \min(\mathsf{OPT}[i-1][j],; \mathsf{OPT}[i][j-1],; \mathsf{OPT}[i-1][j-1]).$$

If $M[i][j] = 0$, then $\mathsf{OPT}[i][j] = 0$. Correctness: extending a square by one row/column requires all three neighboring squares to be at least as large.

ALG(M):
  dp = m x n array, init to M
  best = max entry of dp
  for i = 2, ..., m:
    for j = 2, ..., n:
      if M[i][j] = 1:
        dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
      best = max(best, dp[i][j])
  return best * best

The table has $mn$ entries each computed in $O(1)$, so the total running time is $O(mn)$.

(This is LeetCode 1277.) Use the same DP as Maximal Square (Problem 4.63): $\mathsf{OPT}[i][j]$ = side length of largest all-ones square with bottom-right at $(i,j)$. Cell $(i,j)$ contributes exactly $\mathsf{OPT}[i][j]$ squares (sizes $1 \times 1, 2 \times 2, \ldots$). Return $\sum_{i,j} \mathsf{OPT}[i][j]$.

ALG(M):
  dp = m x n array, init to M
  for i = 2, ..., m:
    for j = 2, ..., n:
      if M[i][j] = 1:
        dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
  return sum of all dp[i][j]

The table has $mn$ entries each computed in $O(1)$, so the total running time is $O(mn)$.

(This is LeetCode 174.) We work backwards. Let $\mathsf{OPT}[i][j]$ = min health needed when entering cell $(i,j)$. Base case: $\mathsf{OPT}[m][n] = \max(1, 1 - G[m][n])$. Recurrence (filling right-to-left, bottom-to-top):

$$\mathsf{OPT}[i][j] = \max\bigl(1,; \min(\mathsf{OPT}[i+1][j],; \mathsf{OPT}[i][j+1]) - G[i][j]\bigr).$$

The knight needs enough health at $(i,j)$ so that after absorbing $G[i][j]$, it has at least the health needed for the better of the two next cells. Return $\mathsf{OPT}[1][1]$.

ALG(G):
  dp = m x n array
  dp[m][n] = max(1, 1 - G[m][n])
  for j = n-1, ..., 1: dp[m][j] = max(1, dp[m][j+1] - G[m][j])
  for i = m-1, ..., 1: dp[i][n] = max(1, dp[i+1][n] - G[i][n])
  for i = m-1, ..., 1:
    for j = n-1, ..., 1:
      dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - G[i][j])
  return dp[1][1]

The table has $mn$ entries each computed in $O(1)$, so the total running time is $O(mn)$.

(This is LeetCode 85.) Build a histogram for each row: let $H[i][j]$ = number of consecutive $1$’s above and including $(i,j)$ in column $j$. Then $H[1][j] = M[1][j]$, and $H[i][j] = H[i-1][j] + 1$ if $M[i][j] = 1$, else $0$. For each row, find the largest rectangle in the histogram. The largest-rectangle-in-histogram problem can be solved in $O(n)$ using a stack.

ALG(M):
  H = [0] * n
  best = 0
  for i = 1, ..., m:
    for j = 1, ..., n:
      if M[i][j] = 1: H[j] += 1
      else: H[j] = 0
    best = max(best, LARGEST_RECT_IN_HISTOGRAM(H))
  return best

LARGEST_RECT_IN_HISTOGRAM uses a stack: for each bar, pop while the stack’s top is taller, compute the rectangle area formed. This runs in $O(n)$ amortized. Over $m$ rows, total: $O(mn)$.

(This is LeetCode 1301.) Let $\mathsf{SCORE}[i][j]$ and $\mathsf{CNT}[i][j]$ = max score and path count to reach $(i,j)$ from the bottom-right. Start at $(n,n)$ with score $0$ and count $1$. Process right-to-left, bottom-to-top:

$$\mathsf{SCORE}[i][j] = G[i][j] + \max(\mathsf{SCORE}[i+1][j],; \mathsf{SCORE}[i][j+1],; \mathsf{SCORE}[i+1][j+1]).$$

$\mathsf{CNT}[i][j]$ sums the counts of whichever neighbor(s) achieve the max. Blocked cells get score $-1$. Return $[\mathsf{SCORE}[1][1], \mathsf{CNT}[1][1]]$.

ALG(G):
  score = n x n array, init -1; cnt = n x n array, init 0
  score[n][n] = 0; cnt[n][n] = 1
  for i = n, ..., 1:
    for j = n, ..., 1:
      if (i,j) = (n,n) or G[i][j] = 'X': continue
      for (di,dj) in {(1,0),(0,1),(1,1)}:
        ni, nj = i+di, j+dj
        if in bounds and score[ni][nj] >= 0:
          val = score[ni][nj] + digit(G[i][j])
          if val > score[i][j]:
            score[i][j] = val; cnt[i][j] = cnt[ni][nj]
          else if val = score[i][j]:
            cnt[i][j] += cnt[ni][nj]
  return [score[1][1], cnt[1][1]]

$O(n^2)$ cells, $O(1)$ per cell. Total: $O(n^2)$.

(This is LeetCode 2304.) Let $\mathsf{OPT}[i][j]$ = min cost to reach cell $(i,j)$. Base case: $\mathsf{OPT}[1][j] = G[1][j]$. Recurrence:

$$\mathsf{OPT}[i][j] = G[i][j] + \min_{c=1}^{n} (\mathsf{OPT}[i-1][c] + \text{cost}[G[i-1][c]][j]).$$

ALG(G, cost):
  dp = copy of G[1]
  for i = 2, ..., m:
    new_dp = [inf] * n
    for c = 1, ..., n:
      for j = 1, ..., n:
        new_dp[j] = min(new_dp[j], dp[c] + cost[G[i-1][c]][j] + G[i][j])
    dp = new_dp
  return min(dp)

For each row, we try all $n \times n$ (source, dest) pairs, so each row costs $O(n^2)$. Total: $O(mn^2)$.

(This is LeetCode 1143.) Let $\mathsf{OPT}[i][j]$ = LCS length for $X[1 ,:, i]$ and $Y[1 ,:, j]$. Base case: $\mathsf{OPT}[0][j] = \mathsf{OPT}[i][0] = 0$. Recurrence:

$$\mathsf{OPT}[i][j] = \begin{cases} \mathsf{OPT}[i-1][j-1] + 1 & \text{if } X[i] = Y[j] \ \max(\mathsf{OPT}[i-1][j],; \mathsf{OPT}[i][j-1]) & \text{otherwise.} \end{cases}$$

If the last elements match, they extend the LCS; otherwise, one of them is excluded.

ALG(X, Y):
  dp = (m+1) x (n+1) array, init to 0
  for i = 1, ..., m:
    for j = 1, ..., n:
      if X[i] = Y[j]:
        dp[i][j] = dp[i-1][j-1] + 1
      else:
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  return dp[m][n]

The table has $(m+1)(n+1)$ entries each computed in $O(1)$. Total: $O(mn)$.

(This is LeetCode 72.) Let $\mathsf{OPT}[i][j]$ = edit distance between $X[1 ,:, i]$ and $Y[1 ,:, j]$. Base cases: $\mathsf{OPT}[0][j] = j$ (insert $j$ elements), $\mathsf{OPT}[i][0] = i$ (delete $i$ elements). Recurrence:

$$\mathsf{OPT}[i][j] = \begin{cases} \mathsf{OPT}[i-1][j-1] & \text{if } X[i] = Y[j] \ 1 + \min(\mathsf{OPT}[i-1][j],; \mathsf{OPT}[i][j-1],; \mathsf{OPT}[i-1][j-1]) & \text{otherwise.} \end{cases}$$

The three choices are delete from $X$, insert into $X$, and replace.

ALG(X, Y):
  dp = (m+1) x (n+1) array
  for i = 0, ..., m: dp[i][0] = i
  for j = 0, ..., n: dp[0][j] = j
  for i = 1, ..., m:
    for j = 1, ..., n:
      if X[i] = Y[j]:
        dp[i][j] = dp[i-1][j-1]
      else:
        dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
  return dp[m][n]

The table has $(m+1)(n+1)$ entries each computed in $O(1)$. Total: $O(mn)$.

(This is LeetCode 516.) Let $\mathsf{OPT}[i][j]$ = length of longest palindromic subsequence in $A[i ,:, j]$. Base case: $\mathsf{OPT}[i][i] = 1$. Recurrence:

$$\mathsf{OPT}[i][j] = \begin{cases} \mathsf{OPT}[i+1][j-1] + 2 & \text{if } A[i] = A[j] \ \max(\mathsf{OPT}[i+1][j],; \mathsf{OPT}[i][j-1]) & \text{otherwise.} \end{cases}$$

If the endpoints match, they extend the palindrome; otherwise, drop one endpoint. Fill the table by increasing length $\ell = j - i + 1$.

ALG(A):
  dp = n x n array, init to 0
  for i = 1, ..., n: dp[i][i] = 1
  for len = 2, ..., n:
    for i = 1, ..., n - len + 1:
      j = i + len - 1
      if A[i] = A[j]:
        dp[i][j] = dp[i+1][j-1] + 2
      else:
        dp[i][j] = max(dp[i+1][j], dp[i][j-1])
  return dp[1][n]

There are $O(n^2)$ subproblems each computed in $O(1)$. Total: $O(n^2)$.

(This is LeetCode 5.) Let $\mathsf{OPT}[i][j]$ = true if $A[i ,:, j]$ is a palindrome. Base cases: $\mathsf{OPT}[i][i] = \text{true}$, $\mathsf{OPT}[i][i+1] = (A[i] = A[i+1])$. Recurrence:

$$\mathsf{OPT}[i][j] = (A[i] = A[j]) ;\land; \mathsf{OPT}[i+1][j-1].$$

Track the longest palindrome found.

ALG(A):
  dp = n x n boolean array, init to false
  best = 1
  for i = 1, ..., n: dp[i][i] = true
  for i = 1, ..., n-1:
    if A[i] = A[i+1]: dp[i][i+1] = true; best = 2
  for len = 3, ..., n:
    for i = 1, ..., n - len + 1:
      j = i + len - 1
      if A[i] = A[j] and dp[i+1][j-1]:
        dp[i][j] = true
        best = len
  return best

There are $O(n^2)$ subproblems each computed in $O(1)$. Total: $O(n^2)$.

(This is LeetCode 647.) Use the same DP table as Longest Palindromic Substring (Problem 4.72): $\mathsf{OPT}[i][j] = \text{true}$ iff $A[i ,:, j]$ is a palindrome. The answer is $\sum_{i \leq j} [\mathsf{OPT}[i][j] = \text{true}]$.

ALG(A):
  count = n  # singletons
  dp = n x n boolean, init to false
  for i = 1, ..., n: dp[i][i] = true
  for i = 1, ..., n-1:
    if A[i] = A[i+1]: dp[i][i+1] = true; count += 1
  for len = 3, ..., n:
    for i = 1, ..., n - len + 1:
      j = i + len - 1
      if A[i] = A[j] and dp[i+1][j-1]:
        dp[i][j] = true; count += 1
  return count

There are $O(n^2)$ subproblems each computed in $O(1)$. Total: $O(n^2)$.

(This is LeetCode 712.) Let $\mathsf{OPT}[i][j]$ = min deletion cost to make $X[1 ,:, i]$ and $Y[1 ,:, j]$ equal. Base cases: $\mathsf{OPT}[0][j] = \sum_{k=1}^{j} Y[k]$, $\mathsf{OPT}[i][0] = \sum_{k=1}^{i} X[k]$. Recurrence:

$$\mathsf{OPT}[i][j] = \begin{cases} \mathsf{OPT}[i-1][j-1] & \text{if } X[i] = Y[j] \ \min(\mathsf{OPT}[i-1][j] + X[i],; \mathsf{OPT}[i][j-1] + Y[j]) & \text{otherwise.} \end{cases}$$

ALG(X, Y):
  dp = (m+1) x (n+1) array
  dp[0][0] = 0
  for i = 1, ..., m: dp[i][0] = dp[i-1][0] + X[i]
  for j = 1, ..., n: dp[0][j] = dp[0][j-1] + Y[j]
  for i = 1, ..., m:
    for j = 1, ..., n:
      if X[i] = Y[j]:
        dp[i][j] = dp[i-1][j-1]
      else:
        dp[i][j] = min(dp[i-1][j] + X[i], dp[i][j-1] + Y[j])
  return dp[m][n]

The table has $(m+1)(n+1)$ entries each computed in $O(1)$. Total: $O(mn)$.

(This is LeetCode 115.) Let $\mathsf{OPT}[i][j]$ = number of subsequences of $S[1 ,:, i]$ that equal $T[1 ,:, j]$. Base cases: $\mathsf{OPT}[i][0] = 1$ (empty $T$ is always a subsequence), $\mathsf{OPT}[0][j] = 0$ for $j > 0$. Recurrence:

$$\mathsf{OPT}[i][j] = \mathsf{OPT}[i-1][j] + \begin{cases} \mathsf{OPT}[i-1][j-1] & \text{if } S[i] = T[j] \ 0 & \text{otherwise.} \end{cases}$$

We either skip $S[i]$ (first term) or match it with $T[j]$ if they agree.

ALG(S, T):
  dp = (m+1) x (n+1) array, init to 0
  for i = 0, ..., m: dp[i][0] = 1
  for i = 1, ..., m:
    for j = 1, ..., n:
      dp[i][j] = dp[i-1][j]
      if S[i] = T[j]:
        dp[i][j] += dp[i-1][j-1]
  return dp[m][n]

The table has $(m+1)(n+1)$ entries each computed in $O(1)$. Total: $O(mn)$.

(This is LeetCode 97.) Let $\mathsf{OPT}[i][j]$ = true if $C[1 ,:, i+j]$ is an interleaving of $A[1 ,:, i]$ and $B[1 ,:, j]$. Base case: $\mathsf{OPT}[0][0] = \text{true}$. Recurrence:

$$\mathsf{OPT}[i][j] = (\mathsf{OPT}[i-1][j] \land A[i] = C[i+j]) ;\lor; (\mathsf{OPT}[i][j-1] \land B[j] = C[i+j]).$$

The last element of $C[1 ,:, i+j]$ comes from either $A[i]$ or $B[j]$. Return $\mathsf{OPT}[m][n]$.

ALG(A, B, C):
  if m + n != len(C): return false
  dp = (m+1) x (n+1) boolean, init false
  dp[0][0] = true
  for i = 1, ..., m: dp[i][0] = dp[i-1][0] and (A[i] = C[i])
  for j = 1, ..., n: dp[0][j] = dp[0][j-1] and (B[j] = C[j])
  for i = 1, ..., m:
    for j = 1, ..., n:
      dp[i][j] = (dp[i-1][j] and A[i] = C[i+j]) or
                 (dp[i][j-1] and B[j] = C[i+j])
  return dp[m][n]

The table has $(m+1)(n+1)$ entries each computed in $O(1)$. Total: $O(mn)$.

(This is LeetCode 44.) Let $\mathsf{OPT}[i][j]$ = true if $P[1 ,:, j]$ matches $S[1 ,:, i]$. Base case: $\mathsf{OPT}[0][0] = \text{true}$; $\mathsf{OPT}[0][j] = \text{true}$ if $P[1], \ldots, P[j]$ are all $\text{*}$. Recurrence:

• If $P[j] = \text{*}$: $\mathsf{OPT}[i][j] = \mathsf{OPT}[i-1][j] \lor \mathsf{OPT}[i][j-1]$ (match one more element or match empty).
• If $P[j] = \text{?}$ or $P[j] = S[i]$: $\mathsf{OPT}[i][j] = \mathsf{OPT}[i-1][j-1]$.
• Otherwise: $\mathsf{OPT}[i][j] = \text{false}$.

ALG(S, P):
  dp = (m+1) x (n+1) boolean, init false
  dp[0][0] = true
  for j = 1, ..., n:
    if P[j] = '*': dp[0][j] = dp[0][j-1]
  for i = 1, ..., m:
    for j = 1, ..., n:
      if P[j] = '*':
        dp[i][j] = dp[i-1][j] or dp[i][j-1]
      else if P[j] = '?' or P[j] = S[i]:
        dp[i][j] = dp[i-1][j-1]
  return dp[m][n]

The table has $(m+1)(n+1)$ entries each computed in $O(1)$. Total: $O(mn)$.

(This is LeetCode 1092.) The length of the shortest common supersequence is $m + n - \text{LCS}(X, Y)$. The elements in the LCS are shared, and the remaining elements are inserted. So first compute LCS length using Problem 4.69, then return $m + n - \mathsf{OPT}[m][n]$.

ALG(X, Y):
  # Compute LCS table
  dp = (m+1) x (n+1) array, init to 0
  for i = 1, ..., m:
    for j = 1, ..., n:
      if X[i] = Y[j]:
        dp[i][j] = dp[i-1][j-1] + 1
      else:
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  return m + n - dp[m][n]

The LCS computation takes $O(mn)$. Total: $O(mn)$.

(This is LeetCode 1035.) Non-crossing lines correspond exactly to a common subsequence, so this is the Longest Common Subsequence problem (Problem 4.69). Use the same algorithm.

ALG(A, B):
  dp = (m+1) x (n+1) array, init to 0
  for i = 1, ..., m:
    for j = 1, ..., n:
      if A[i] = B[j]:
        dp[i][j] = dp[i-1][j-1] + 1
      else:
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  return dp[m][n]

The table has $(m+1)(n+1)$ entries each computed in $O(1)$. Total: $O(mn)$.

(This is LeetCode 718.) Let $\mathsf{OPT}[i][j]$ = length of the longest common suffix of $A[1 ,:, i]$ and $B[1 ,:, j]$. Base case: $\mathsf{OPT}[0][j] = \mathsf{OPT}[i][0] = 0$. Recurrence:

$$\mathsf{OPT}[i][j] = \begin{cases} \mathsf{OPT}[i-1][j-1] + 1 & \text{if } A[i] = B[j] \ 0 & \text{otherwise.} \end{cases}$$

Return $\max_{i,j} \mathsf{OPT}[i][j]$.

ALG(A, B):
  dp = (m+1) x (n+1) array, init to 0
  best = 0
  for i = 1, ..., m:
    for j = 1, ..., n:
      if A[i] = B[j]:
        dp[i][j] = dp[i-1][j-1] + 1
        best = max(best, dp[i][j])
  return best

The table has $(m+1)(n+1)$ entries each computed in $O(1)$. Total: $O(mn)$.

(This is LeetCode 132.) First, precompute $\mathsf{PAL}[i][j]$ = true if $A[i ,:, j]$ is a palindrome (using the DP from Problem 4.72). Then let $\mathsf{OPT}[i]$ = min cuts for $A[1 ,:, i]$. Base case: $\mathsf{OPT}[0] = -1$ (no elements, no cuts). Recurrence:

$$\mathsf{OPT}[i] = \min_{j \leq i,; \mathsf{PAL}[j][i]} (\mathsf{OPT}[j-1] + 1).$$

The last palindromic piece is $A[j ,:, i]$; we try all valid starting positions $j$.

ALG(A):
  # Precompute palindrome table
  pal = n x n boolean; fill as in Problem 4.72
  # Min cuts
  d = [inf] * (n+1)
  d[0] = -1
  for i = 1, ..., n:
    for j = 1, ..., i:
      if pal[j][i]:
        d[i] = min(d[i], d[j-1] + 1)
  return d[n]

The palindrome table costs $O(n^2)$; the DP also has $O(n^2)$ transitions. Total: $O(n^2)$.

(This is LeetCode 1312.) The minimum insertions equals $n - \text{LPS}(A)$, where $\text{LPS}$ is the longest palindromic subsequence. We keep the longest palindromic subsequence intact and insert elements to match the rest. Use the algorithm from Problem 4.71 and return $n - \mathsf{OPT}[1][n]$.

ALG(A):
  dp = n x n array, init to 0
  for i = 1, ..., n: dp[i][i] = 1
  for len = 2, ..., n:
    for i = 1, ..., n - len + 1:
      j = i + len - 1
      if A[i] = A[j]:
        dp[i][j] = dp[i+1][j-1] + 2
      else:
        dp[i][j] = max(dp[i+1][j], dp[i][j-1])
  return n - dp[1][n]

There are $O(n^2)$ subproblems each computed in $O(1)$. Total: $O(n^2)$.

(This is LeetCode 312.) Pad $A$ with $1$s: $B[0] = B[n+1] = 1$, $B[i] = A[i]$. Let $\mathsf{OPT}[l][r]$ = max coins from bursting all balloons in $(l, r)$ (exclusive). If balloon $k$ is the last one burst in the range, the adjacent values are $B[l]$ and $B[r]$ (all others already gone). Recurrence:

$$\mathsf{OPT}[l][r] = \max_{k=l+1}^{r-1} \bigl(B[l] \cdot B[k] \cdot B[r] + \mathsf{OPT}[l][k] + \mathsf{OPT}[k][r]\bigr).$$

Base case: $\mathsf{OPT}[l][r] = 0$ when $r - l \leq 1$ (no balloons between). Return $\mathsf{OPT}[0][n+1]$.

ALG(A):
  B = [1] + A + [1]
  N = len(B)
  dp = N x N array, init to 0
  for gap = 2, ..., N-1:
    for l = 0, ..., N - gap - 1:
      r = l + gap
      for k = l+1, ..., r-1:
        dp[l][r] = max(dp[l][r], B[l]*B[k]*B[r] + dp[l][k] + dp[k][r])
  return dp[0][N-1]

There are $O(n^2)$ intervals, each trying $O(n)$ split points, so the total running time is $O(n^3)$.

Let $\mathsf{OPT}[i][j]$ = min multiplications to compute $M_i \cdots M_j$. Base case: $\mathsf{OPT}[i][i] = 0$. Recurrence: split between $M_k$ and $M_{k+1}$:

$$\mathsf{OPT}[i][j] = \min_{k=i}^{j-1} \bigl(\mathsf{OPT}[i][k] + \mathsf{OPT}[k+1][j] + P[i-1] \cdot P[k] \cdot P[j]\bigr).$$

The last multiplication combines an $(P[i-1] \times P[k])$ result with a $(P[k] \times P[j])$ result.

ALG(P):
  dp = n x n array, init to 0
  for len = 2, ..., n:
    for i = 1, ..., n - len + 1:
      j = i + len - 1
      dp[i][j] = inf
      for k = i, ..., j - 1:
        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + P[i-1]*P[k]*P[j])
  return dp[1][n]

There are $O(n^2)$ subproblems, each trying $O(n)$ splits. Total: $O(n^3)$.

(This is LeetCode 1039.) Let $\mathsf{OPT}[i][j]$ = min score to triangulate the sub-polygon from vertex $i$ to $j$. Base case: $\mathsf{OPT}[i][j] = 0$ when $j - i < 2$. For each triangle containing edge $(i, j)$, pick the third vertex $k$:

$$\mathsf{OPT}[i][j] = \min_{k=i+1}^{j-1} \bigl(A[i] \cdot A[k] \cdot A[j] + \mathsf{OPT}[i][k] + \mathsf{OPT}[k][j]\bigr).$$

ALG(A):
  dp = n x n array, init to 0
  for len = 3, ..., n:
    for i = 1, ..., n - len + 1:
      j = i + len - 1
      dp[i][j] = inf
      for k = i+1, ..., j-1:
        dp[i][j] = min(dp[i][j], A[i]*A[k]*A[j] + dp[i][k] + dp[k][j])
  return dp[1][n]

There are $O(n^2)$ subproblems, each trying $O(n)$ splits. Total: $O(n^3)$.

(This is LeetCode 1547.) Sort $C$ and add sentinel values $0$ and $n$: $S = [0] + \text{sorted}(C) + [n]$. Let $\mathsf{OPT}[i][j]$ = min cost to make all cuts between positions $S[i]$ and $S[j]$. Base case: $\mathsf{OPT}[i][i+1] = 0$. Recurrence:

$$\mathsf{OPT}[i][j] = (S[j] - S[i]) + \min_{k=i+1}^{j-1} \bigl(\mathsf{OPT}[i][k] + \mathsf{OPT}[k][j]\bigr).$$

The cost of cutting the segment $[S[i], S[j]]$ is its length $S[j] - S[i]$.

ALG(n, C):
  S = [0] + sort(C) + [n]
  L = len(S)
  dp = L x L array, init to 0
  for gap = 2, ..., L - 1:
    for i = 0, ..., L - gap - 1:
      j = i + gap
      dp[i][j] = inf
      for k = i+1, ..., j-1:
        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
      dp[i][j] += S[j] - S[i]
  return dp[0][L-1]

There are $O(m^2)$ subproblems, each trying $O(m)$ splits. Total: $O(m^3)$.

(This is LeetCode 877.) Let $\mathsf{OPT}[i][j]$ = max score difference the current player can achieve from piles $A[i ,:, j]$. Base case: $\mathsf{OPT}[i][i] = A[i]$. Recurrence:

$$\mathsf{OPT}[i][j] = \max(A[i] - \mathsf{OPT}[i+1][j],; A[j] - \mathsf{OPT}[i][j-1]).$$

Taking $A[i]$ earns $A[i]$ but then the opponent gets $\mathsf{OPT}[i+1][j]$; similarly for $A[j]$.

ALG(A):
  dp = n x n array
  for i = 1, ..., n: dp[i][i] = A[i]
  for len = 2, ..., n:
    for i = 1, ..., n - len + 1:
      j = i + len - 1
      dp[i][j] = max(A[i] - dp[i+1][j], A[j] - dp[i][j-1])
  return dp[1][n]

There are $O(n^2)$ subproblems each computed in $O(1)$. Total: $O(n^2)$.

(This is LeetCode 486.) Use the same DP as Stone Game (Problem 4.87): $\mathsf{OPT}[i][j]$ = max score difference for the current player on $A[i ,:, j]$. Return $\mathsf{OPT}[1][n] \geq 0$.

ALG(A):
  dp = n x n array
  for i = 1, ..., n: dp[i][i] = A[i]
  for len = 2, ..., n:
    for i = 1, ..., n - len + 1:
      j = i + len - 1
      dp[i][j] = max(A[i] - dp[i+1][j], A[j] - dp[i][j-1])
  return dp[1][n] >= 0

There are $O(n^2)$ subproblems each computed in $O(1)$. Total: $O(n^2)$.

(This is LeetCode 1140.) Precompute suffix sums $\text{suf}[i] = A[i] + \cdots + A[n]$. Let $\mathsf{OPT}[i][m]$ = max stones the current player can get from piles $A[i ,:, n]$ with parameter $M = m$. Base case: if $i + 2m \geq n$, take all remaining: $\mathsf{OPT}[i][m] = \text{suf}[i]$. Recurrence:

$$\mathsf{OPT}[i][m] = \max_{x=1}^{2m} \bigl(\text{suf}[i] - \mathsf{OPT}[i+x][\max(m, x)]\bigr).$$

Taking $x$ piles gives the current player $\text{suf}[i] - \text{suf}[i+x]$ stones, but the opponent then gets $\mathsf{OPT}[i+x][\max(m, x)]$.

ALG(A):
  suf = suffix sums of A
  dp = (n+1) x (n+1) array, init to 0
  for i = n, ..., 1:
    for m = 1, ..., n:
      if i + 2*m >= n:
        dp[i][m] = suf[i]
      else:
        for x = 1, ..., 2*m:
          dp[i][m] = max(dp[i][m], suf[i] - dp[i+x][max(m, x)])
  return dp[1][1]

There are $O(n^2)$ states, and each tries up to $O(n)$ moves. Total: $O(n^3)$.

(This is LeetCode 1130.) Let $\mathsf{OPT}[i][j]$ = min sum of internal nodes for a tree whose leaves are $A[i ,:, j]$. Base case: $\mathsf{OPT}[i][i] = 0$ (single leaf, no internal nodes). Precompute $\text{mx}[i][j] = \max(A[i ,:, j])$. Recurrence (split at $k$):

$$\mathsf{OPT}[i][j] = \min_{k=i}^{j-1} \bigl(\mathsf{OPT}[i][k] + \mathsf{OPT}[k+1][j] + \text{mx}[i][k] \cdot \text{mx}[k+1][j]\bigr).$$

ALG(A):
  # Precompute range max
  mx = n x n array
  for i = 1, ..., n: mx[i][i] = A[i]
  for len = 2, ..., n:
    for i = 1, ..., n-len+1:
      mx[i][i+len-1] = max(mx[i][i+len-2], A[i+len-1])
  # Interval DP
  dp = n x n array, init to 0
  for len = 2, ..., n:
    for i = 1, ..., n-len+1:
      j = i + len - 1
      dp[i][j] = inf
      for k = i, ..., j-1:
        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + mx[i][k]*mx[k+1][j])
  return dp[1][n]

$O(n^2)$ subproblems, $O(n)$ splits each. Total: $O(n^3)$.

(This is LeetCode 122.) Two states: $\mathsf{HOLD}[i]$ = max profit on day $i$ while holding a share, $\mathsf{CASH}[i]$ = max profit with no share. Recurrences:

$$\mathsf{HOLD}[i] = \max(\mathsf{HOLD}[i-1],; \mathsf{CASH}[i-1] - P[i])$$ $$\mathsf{CASH}[i] = \max(\mathsf{CASH}[i-1],; \mathsf{HOLD}[i-1] + P[i])$$

Base: $\mathsf{HOLD}[1] = -P[1]$, $\mathsf{CASH}[1] = 0$. Return $\mathsf{CASH}[n]$.

ALG(P):
  hold, cash = -P[1], 0
  for i = 2, ..., n:
    hold, cash = max(hold, cash - P[i]), max(cash, hold + P[i])
  return cash

The algorithm makes $n - 1$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 309.) Three states: $\mathsf{HOLD}[i]$ = holding a share, $\mathsf{SOLD}[i]$ = just sold (in cooldown), $\mathsf{REST}[i]$ = not holding, free to buy. Recurrences:

$$\mathsf{HOLD}[i] = \max(\mathsf{HOLD}[i-1],; \mathsf{REST}[i-1] - P[i])$$ $$\mathsf{SOLD}[i] = \mathsf{HOLD}[i-1] + P[i]$$ $$\mathsf{REST}[i] = \max(\mathsf{REST}[i-1],; \mathsf{SOLD}[i-1])$$

Base: $\mathsf{HOLD}[1] = -P[1]$, $\mathsf{SOLD}[1] = 0$, $\mathsf{REST}[1] = 0$. Return $\max(\mathsf{SOLD}[n], \mathsf{REST}[n])$.

ALG(P):
  hold, sold, rest = -P[1], 0, 0
  for i = 2, ..., n:
    hold, sold, rest = max(hold, rest - P[i]), hold + P[i], max(rest, sold)
  return max(sold, rest)

The algorithm makes $n - 1$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 714.) Two states: $\mathsf{HOLD}[i]$ = holding a share, $\mathsf{CASH}[i]$ = not holding. Recurrences:

$$\mathsf{HOLD}[i] = \max(\mathsf{HOLD}[i-1],; \mathsf{CASH}[i-1] - P[i])$$ $$\mathsf{CASH}[i] = \max(\mathsf{CASH}[i-1],; \mathsf{HOLD}[i-1] + P[i] - \text{fee})$$

Base: $\mathsf{HOLD}[1] = -P[1]$, $\mathsf{CASH}[1] = 0$. Return $\mathsf{CASH}[n]$.

ALG(P, fee):
  hold, cash = -P[1], 0
  for i = 2, ..., n:
    hold, cash = max(hold, cash - P[i]), max(cash, hold + P[i] - fee)
  return cash

The algorithm makes $n - 1$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 123.) Maintain four states: $b_1$ = max profit after first buy, $s_1$ = after first sell, $b_2$ = after second buy, $s_2$ = after second sell. Initialize $b_1 = b_2 = -\infty$, $s_1 = s_2 = 0$. For each day:

$$b_1 = \max(b_1, -P[i]), \quad s_1 = \max(s_1, b_1 + P[i])$$ $$b_2 = \max(b_2, s_1 - P[i]), \quad s_2 = \max(s_2, b_2 + P[i])$$

Return $s_2$.

ALG(P):
  b1, s1, b2, s2 = -inf, 0, -inf, 0
  for i = 1, ..., n:
    b1 = max(b1, -P[i])
    s1 = max(s1, b1 + P[i])
    b2 = max(b2, s1 - P[i])
    s2 = max(s2, b2 + P[i])
  return s2

The algorithm makes $n$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 188.) If $k \geq n/2$, we can make unlimited transactions (use the algorithm from Problem 4.91). Otherwise, let $\mathsf{BUY}[t]$ and $\mathsf{SELL}[t]$ = max profit after the $t$-th buy and $t$-th sell. Initialize $\mathsf{BUY}[t] = -\infty$, $\mathsf{SELL}[t] = 0$. For each day:

$$\mathsf{BUY}[t] = \max(\mathsf{BUY}[t],; \mathsf{SELL}[t-1] - P[i])$$ $$\mathsf{SELL}[t] = \max(\mathsf{SELL}[t],; \mathsf{BUY}[t] + P[i])$$

for $t = 1, \ldots, k$. Return $\mathsf{SELL}[k]$.

ALG(P, k):
  if k >= n/2: return unlimited-transactions solution
  buy = [-inf] * (k+1)
  sell = [0] * (k+1)
  for i = 1, ..., n:
    for t = 1, ..., k:
      buy[t] = max(buy[t], sell[t-1] - P[i])
      sell[t] = max(sell[t], buy[t] + P[i])
  return sell[k]

There are $n$ days and $k$ transactions per day, so the total running time is $O(nk)$.

(This is LeetCode 1567.) Maintain $\mathsf{POS}[i]$ = length of longest subarray ending at $i$ with positive product, and $\mathsf{NEG}[i]$ = length with negative product. If $A[i] = 0$, reset both to $0$. If $A[i] > 0$: $\mathsf{POS}[i] = \mathsf{POS}[i-1] + 1$, $\mathsf{NEG}[i] = \mathsf{NEG}[i-1] + 1$ (if $\mathsf{NEG}[i-1] > 0$, else $0$). If $A[i] < 0$: $\mathsf{POS}[i] = \mathsf{NEG}[i-1] + 1$ (if $\mathsf{NEG}[i-1] > 0$, else $0$), $\mathsf{NEG}[i] = \mathsf{POS}[i-1] + 1$.

ALG(A):
  pos, neg, best = 0, 0, 0
  for i = 1, ..., n:
    if A[i] = 0:
      pos, neg = 0, 0
    else if A[i] > 0:
      pos += 1
      neg = neg + 1 if neg > 0 else 0
    else:
      pos, neg = (neg + 1 if neg > 0 else 0), pos + 1
    best = max(best, pos)
  return best

The algorithm makes $n$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 1770.) Let $\mathsf{OPT}[i][j]$ = max score using the first $i + j$ multipliers, taking $i$ from the left and $j$ from the right of $A$. The multiplier index is $i + j$. Base case: $\mathsf{OPT}[0][0] = 0$. Recurrence:

$$\mathsf{OPT}[i][j] = \max\bigl(\mathsf{OPT}[i-1][j] + A[i] \cdot M[i+j],; \mathsf{OPT}[i][j-1] + A[n-j+1] \cdot M[i+j]\bigr).$$

Subject to $i + j \leq m$. Return $\max_{i+j=m} \mathsf{OPT}[i][j]$.

ALG(A, M):
  dp = (m+1) x (m+1) array, init to -inf
  dp[0][0] = 0
  for i = 0, ..., m:
    for j = 0, ..., m - i:
      if i > 0:
        dp[i][j] = max(dp[i][j], dp[i-1][j] + A[i] * M[i+j])
      if j > 0:
        dp[i][j] = max(dp[i][j], dp[i][j-1] + A[n-j+1] * M[i+j])
  return max of dp[i][j] where i + j = m

The table has $O(m^2)$ entries, each computed in $O(1)$. Total: $O(m^2)$.

(This is LeetCode 1335.) If $n < d$, return $-1$. Let $\mathsf{OPT}[i][k]$ = min difficulty for jobs $1, \ldots, i$ over $k$ days. Base case: $\mathsf{OPT}[i][1] = \max(A[1 ,:, i])$. Recurrence:

$$\mathsf{OPT}[i][k] = \min_{j=k}^{i} \bigl(\mathsf{OPT}[j-1][k-1] + \max(A[j ,:, i])\bigr).$$

Day $k$ handles jobs $j, \ldots, i$ with difficulty $\max(A[j ,:, i])$.

ALG(A, d):
  if n < d: return -1
  dp = (n+1) x (d+1) array, init to inf
  dp[0][0] = 0
  for k = 1, ..., d:
    for i = k, ..., n:
      curMax = 0
      for j = i, ..., k:
        curMax = max(curMax, A[j])
        dp[i][k] = min(dp[i][k], dp[j-1][k-1] + curMax)
  return dp[n][d]

For each day $k$, we fill $O(n)$ entries, each scanning $O(n)$ jobs. Total: $O(n^2 d)$.

(This is LeetCode 1235.) Sort jobs by end time. Let $\mathsf{OPT}[i]$ = max profit considering the first $i$ jobs. For job $i$, binary search for the latest job $j$ with $e_j \leq s_i$. Recurrence:

$$\mathsf{OPT}[i] = \max(\mathsf{OPT}[i-1],; p_i + \mathsf{OPT}[j]).$$

Either skip job $i$ or take it (adding profit to the best compatible set).

ALG(jobs):
  sort jobs by end time
  d = [0] * (n+1)
  for i = 1, ..., n:
    j = binary search for latest job with end <= start[i]
    d[i] = max(d[i-1], profit[i] + d[j])
  return d[n]

Sorting costs $O(n \log n)$. Each of $n$ subproblems does a binary search in $O(\log n)$. Total: $O(n \log n)$.

(This is LeetCode 1411.) Each row of $3$ cells has two pattern types: ABA (two colors, e.g., red-green-red) and ABC (three distinct colors). There are $6$ ABA patterns and $6$ ABC patterns ($12$ total for one row).

For transitions: an ABA row can be followed by $3$ ABA and $2$ ABC patterns. An ABC row can be followed by $2$ ABA and $2$ ABC patterns. Let $a_i$ and $b_i$ count ABA and ABC patterns at row $i$:

$$a_i = 3 a_{i-1} + 2 b_{i-1}, \quad b_i = 2 a_{i-1} + 2 b_{i-1}.$$

Base: $a_1 = 6, b_1 = 6$. Return $a_n + b_n$.

ALG(n):
  a, b = 6, 6
  for i = 2, ..., n:
    a, b = 3*a + 2*b, 2*a + 2*b
  return a + b

The algorithm makes $n - 1$ iterations each taking $O(1)$ time, so the total running time is $O(n)$.

(This is LeetCode 1359.) After placing the first $i-1$ orders ($2(i-1)$ events), we insert $P_i$ and $D_i$. There are $2(i-1) + 1$ positions for $P_i$, and once $P_i$ is placed at some position, $D_i$ can go in any later position. If $P_i$ goes in position $k$, $D_i$ has $2(i-1) + 2 - k$ choices. Summing over $k$: total ways = $(2i-1) \cdot i$ (by the formula $\sum_{k=1}^{2i-1} (2i - k) = i(2i-1)$). Recurrence:

$$\mathsf{OPT}[i] = \mathsf{OPT}[i-1] \cdot i \cdot (2i - 1).$$

Base: $\mathsf{OPT}[1] = 1$.

ALG(n):
  result = 1
  for i = 2, ..., n:
    result *= i * (2*i - 1)
  return result

The algorithm makes $n - 1$ multiplications, so the total running time is $O(n)$.

(This is LeetCode 446.) For each index $i$ and common difference $d$, let $f[i][d]$ = number of arithmetic subsequences of length $\geq 2$ ending at $i$ with difference $d$. For each pair $(j, i)$ with $j < i$:

$$d = A[i] - A[j]; \quad \text{count} += f[j][d]; \quad f[i][d] += f[j][d] + 1.$$

We add $f[j][d]$ to the count because each length-$\geq 2$ subsequence ending at $j$ extends to length $\geq 3$ at $i$. The $+1$ starts a new pair $(A[j], A[i])$. Use a hash map for each $i$.

ALG(A):
  f = array of n hash maps
  count = 0
  for i = 1, ..., n:
    for j = 1, ..., i-1:
      d = A[i] - A[j]
      count += f[j].get(d, 0)
      f[i][d] += f[j].get(d, 0) + 1
  return count

There are $O(n^2)$ pairs, each doing $O(1)$ hash map operations. Total: $O(n^2)$.

(This is LeetCode 2209.) Precompute prefix sums $S$ of $F$. Let $\mathsf{OPT}[i][j]$ = min white tiles in $F[1 ,:, i]$ using $j$ carpets. Base case: $\mathsf{OPT}[i][0] = S[i]$. Recurrence:

$$\mathsf{OPT}[i][j] = \min\bigl(\mathsf{OPT}[i-1][j] + F[i],; \mathsf{OPT}[\max(0, i-\text{len})][j-1]\bigr).$$

Either tile $i$ is uncovered (first term), or a carpet covers tiles $i-\text{len}+1$ through $i$.

ALG(F, k, len):
  S = prefix sums of F
  dp = (n+1) x (k+1) array
  for i = 0, ..., n: dp[i][0] = S[i]
  for j = 1, ..., k: dp[0][j] = 0
  for i = 1, ..., n:
    for j = 1, ..., k:
      dp[i][j] = dp[i-1][j] + F[i]
      prev = max(0, i - len)
      dp[i][j] = min(dp[i][j], dp[prev][j-1])
  return dp[n][k]

The table has $O(nk)$ entries each computed in $O(1)$. Total: $O(nk)$.

(This is LeetCode 368.) Sort $A$ in increasing order. Let $\mathsf{OPT}[i]$ = size of largest divisible subset ending with $A[i]$. Base: $\mathsf{OPT}[i] = 1$. Recurrence:

$$\mathsf{OPT}[i] = 1 + \max_{j < i,; A[i] \bmod A[j] = 0} \mathsf{OPT}[j].$$

Since $A$ is sorted and all elements in the subset ending at $j$ divide $A[j]$, they also divide $A[i]$ (transitivity of divisibility). Return $\max(\mathsf{OPT})$.

ALG(A):
  sort A
  d = [1] * n
  for i = 2, ..., n:
    for j = 1, ..., i-1:
      if A[i] mod A[j] = 0:
        d[i] = max(d[i], d[j] + 1)
  return max(d)

Sorting costs $O(n \log n)$. The DP has $O(n^2)$ transitions. Total: $O(n^2)$.

(This is LeetCode 354.) Sort by width ascending; break ties by height descending. Then find the LIS of heights. The width sort ensures nesting in width; breaking ties by descending height prevents using two envelopes with the same width.

The LIS can be found in $O(n \log n)$ using patience sorting (maintain a list of smallest tails).

ALG(envelopes):
  sort by (w ascending, h descending)
  heights = [h for (w, h) in sorted envelopes]
  # LIS on heights using binary search
  tails = []
  for h in heights:
    pos = bisect_left(tails, h)
    if pos = len(tails):
      tails.append(h)
    else:
      tails[pos] = h
  return len(tails)

Sorting costs $O(n \log n)$. The LIS computation does $n$ binary searches, each $O(\log n)$. Total: $O(n \log n)$.

(This is LeetCode 1671.) Compute $\mathsf{LIS}[i]$ = length of LIS ending at $A[i]$, and $\mathsf{LDS}[i]$ = length of longest decreasing subsequence starting at $A[i]$ (equivalently, LIS from right). The longest mountain subsequence centered at $i$ has length $\mathsf{LIS}[i] + \mathsf{LDS}[i] - 1$, but only if both $\geq 2$ (must have both increasing and decreasing parts). Return $n - \max_i(\mathsf{LIS}[i] + \mathsf{LDS}[i] - 1)$.

ALG(A):
  # Forward LIS
  lis = [1] * n
  for i = 2, ..., n:
    for j = 1, ..., i-1:
      if A[j] < A[i]: lis[i] = max(lis[i], lis[j] + 1)
  # Backward LIS (= LDS from each position)
  lds = [1] * n
  for i = n-1, ..., 1:
    for j = i+1, ..., n:
      if A[j] < A[i]: lds[i] = max(lds[i], lds[j] + 1)
  # Best mountain
  best = 0
  for i = 1, ..., n:
    if lis[i] >= 2 and lds[i] >= 2:
      best = max(best, lis[i] + lds[i] - 1)
  return n - best

Each LIS/LDS computation is $O(n^2)$. Total: $O(n^2)$.

(This is LeetCode 1691.) Since rotation is free, sort each cuboid’s dimensions so that $a \leq b \leq c$ (height = $c$). Then sort cuboids by $(a, b, c)$. This is a variant of LIS: $\mathsf{OPT}[i]$ = max stack height ending with cuboid $i$.

$$\mathsf{OPT}[i] = c_i + \max_{j < i,; a_j \leq a_i \land b_j \leq b_i \land c_j \leq c_i} \mathsf{OPT}[j].$$

It is always optimal to orient with the largest dimension as height: placing the largest dimension vertically maximizes the height contribution while minimizing the footprint (making stacking easier).

ALG(cuboids):
  for each cuboid: sort dimensions so a <= b <= c
  sort cuboids by (a, b, c)
  d = [c[i]] for each i
  for i = 2, ..., n:
    for j = 1, ..., i-1:
      if a[j] <= a[i] and b[j] <= b[i] and c[j] <= c[i]:
        d[i] = max(d[i], d[j] + c[i])
  return max(d)

Sorting costs $O(n \log n)$. The DP has $O(n^2)$ transitions. Total: $O(n^2)$.