Lest I Forget

Index

Core Idea

2 min read

Interval DP

Core: optimal solution for [i, j] is f(some continuous split of the interval).

Dependency order: compute smaller intervals first → iterate by length.

Generic Template

// Base cases (e.g., length 1 or 2 = 0)
 
for len = 2; len <= n; len++:
    // i is start index
    for i = 0; i <= n - len; i++:
        // j is end index
        j = i + len - 1
 
        // Init dp[i][j] (e.g., INF or 0)
 
        // k is split point
        // part of right seg usually
        for k = i; k < j; k++:
            cost = combine(dp[i][k], dp[k/k+1][j]) + merge_cost(i, j)
            dp[i][j] = opt(dp[i][j], cost)

Coordinate vs Index - Rod Cutting

Use when splits are restricted to specific points.

Idea: DP state represents indices of a sorted points array, not physical lengths.

  • Pad array with physical boundaries (e.g., 0 and n) → sort.
  • dp[i][j] = cost for segment from arr[i] to arr[j].
  • merge_cost(i, j) = physical length arr[j] - arr[i].
  • k = index of chosen cut point (i < k < j).

Impl bias

  • I often confuse i and j vs k. In the subproblems and the final answer. There are NO cuts or pops at i and j, but only at k.
  • Also forget to see if max or min - basically carelessness.