Dynamic Programming Basics: States, Transitions, LCS and LIS

Dynamic programming (DP) solves a problem by splitting it into overlapping subproblems, solving each subproblem once, and storing the answer so it can be reused. Whenever plain recursion would recompute the same subproblem over and over, DP turns an exponential search into a polynomial table fill.

Intuition

Take the classic triangle path: start at the top of a number triangle, step to one of the two adjacent numbers in the next row, and maximize the total when you reach the bottom.

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5      best path: 7 -> 3 -> 8 -> 7 -> 5 = 30

There are 2^(rows-1) paths, but the best path from a cell down to the bottom does not care how you reached that cell. So one number per cell is enough: "best sum from here down". Each cell is computed from its two children, and the whole triangle takes O(rows^2).

That small example shows the three properties DP relies on:

• Optimal substructure: an optimal solution is assembled from optimal solutions of subproblems. If one piece of the best path were not optimal, swapping in a better piece would improve the whole path.
• Self-contained state (no hidden history): once a state is solved, later decisions cannot change its value. The state has to capture everything the future depends on; if it does not, add a dimension (for example "holding a stock or not").
• Overlapping subproblems: the same state is reached along many routes, which is why caching it pays off.

A helpful picture: every state is a node, every transition is an edge, and the dependency graph is a DAG. Solving a DP is computing a longest path, shortest path or path count on that DAG in topological order.

The recipe

1. State: say in one sentence what dp[...] means, e.g. "f[i][j] is the LCS length of a[:i] and b[:j]". If you cannot say it, the recurrence will be wrong.
2. Transition: express a state through smaller ones. The usual trick is to look at the last element or the last decision.
3. Base cases: empty prefix, last row, length 0 or 1.
4. Order: every state you read must already be computed (increasing i, increasing interval length, children before parents). Memoization lets recursion find the order for you.
5. Answer: dp[n][m], max(dp), dp[0]... Only after it works, shrink memory.

When to use it in interviews / OAs

• The question asks for a maximum/minimum, the number of ways, or whether something is possible, over a set of choices ("pick some", "split into", "transform A into B").
• A greedy rule exists but you can build a counterexample for it.
• Brute force is exponential while constraints are moderate: n up to about 10^3 suggests O(n^2), up to 10^5 suggests O(n log n).
• The input is a sequence (prefix states), a grid (cell states), or two strings compared together (pairs of prefixes).

Template: triangle and grid paths

def max_triangle_path(tri: list[list[int]]) -> int:
    # best[j] = best sum of a path from (row i, column j) down to the bottom
    best = tri[-1][:]
    for i in range(len(tri) - 2, -1, -1):
        for j in range(i + 1):
            best[j] = tri[i][j] + max(best[j], best[j + 1])
    return best[0]

Going bottom-up removes all boundary checks, and a single row of memory is enough because row i only reads row i + 1. The same pattern solves minimum path sum in a grid: dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]).

Longest common subsequence (LCS)

State: f[i][j] is the LCS length of a[:i] and b[:j]. Look at the last characters. If a[i-1] == b[j-1], match them: f[i-1][j-1] + 1. Otherwise at least one of them is unused: max(f[i-1][j], f[i][j-1]). Using prefix lengths (table size (n+1) x (m+1)) makes the empty prefix a free base case.

def lcs(a: str, b: str) -> str:
    n, m = len(a), len(b)
    # f[i][j] = LCS length of a[:i] and b[:j]
    f = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                f[i][j] = f[i - 1][j - 1] + 1
            else:
                f[i][j] = max(f[i - 1][j], f[i][j - 1])
    # walk back from (n, m) to rebuild one optimal subsequence
    out = []
    i, j = n, m
    while i and j:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1])
            i -= 1
            j -= 1
        elif f[i - 1][j] >= f[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(out))

Edit distance

Same pair-of-prefixes state, but now we minimize the number of insertions, deletions and replacements that turn a into b. Only the previous row is needed, so memory drops to O(m).

def edit_distance(a: str, b: str) -> int:
    n, m = len(a), len(b)
    prev = list(range(m + 1))  # a = "": build b[:j] with j insertions
    for i in range(1, n + 1):
        cur = [i] + [0] * m  # b = "": delete all i characters
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j],  # delete a[i-1]
                                 cur[j - 1],  # insert b[j-1]
                                 prev[j - 1])  # replace a[i-1] with b[j-1]
        prev = cur
    return prev[m]

Longest increasing subsequence (LIS)

O(n^2): DP over the last element

f[i] is the length of the longest increasing subsequence that ends at index i; it extends the best f[j] with j < i and a[j] < a[i].

def lis_quadratic(a: list[int]) -> int:
    f = [1] * len(a)  # f[i] = LIS length ending exactly at index i
    for i in range(len(a)):
        for j in range(i):
            if a[j] < a[i]:
                f[i] = max(f[i], f[j] + 1)
    return max(f, default=0)

O(n log n): keep the smallest tails

Maintain tails[k] = the smallest possible last value of an increasing subsequence of length k + 1. A smaller tail is never worse, because it leaves more room for future elements. tails stays sorted, so for each x binary-search the first tail that x can replace; if there is none, x extends the longest subsequence. For a strictly increasing LIS replace the first tail >= x (bisect_left); for non-decreasing replace the first tail > x (bisect_right).

from bisect import bisect_left, bisect_right


def lis_length(a: list[int], strict: bool = True) -> int:
    tails: list[int] = []  # tails[k] = smallest tail of a subsequence of length k + 1
    find = bisect_left if strict else bisect_right
    for x in a:
        k = find(tails, x)
        if k == len(tails):
            tails.append(x)
        else:
            tails[k] = x
    return len(tails)

tails is not an actual subsequence of the input. To rebuild one, remember the index stored at each tail position and, for every element, which index came before it:

def lis_sequence(a: list[int]) -> list[int]:
    tails: list[int] = []  # tail values, as in lis_length
    tail_idx: list[int] = []  # index in a of each tail
    parent = [-1] * len(a)  # previous index in the subsequence ending at i
    for i, x in enumerate(a):
        k = bisect_left(tails, x)
        if k == len(tails):
            tails.append(x)
            tail_idx.append(i)
        else:
            tails[k] = x
            tail_idx[k] = i
        parent[i] = tail_idx[k - 1] if k else -1
    seq = []
    i = tail_idx[-1] if tail_idx else -1
    while i != -1:
        seq.append(a[i])
        i = parent[i]
    return seq[::-1]

Complexity

Problem	Time	Space
Triangle / grid path	O(cells)	O(row width)
LCS with reconstruction	O(nm)	O(nm)
Edit distance (value only)	O(nm)	O(m)
LIS, simple DP	O(n^2)	O(n)
LIS, smallest tails	O(n log n)	O(n)

Common pitfalls

• Fuzzy state: "dp[i] is the answer for i" is not a definition. Say whether it means "ending at i" or "within the first i", because the transitions differ.
• Off-by-one: mixing 0-based string indices with 1-based table indices. Prefix lengths (a[i-1] is the i-th character) keep base cases clean.
• Wrong evaluation order: reading dp[i+1] while filling left to right. Check which neighbors each transition reads.
• Bad initial values: a max-DP over possibly negative numbers must start from negative infinity, not 0.
• LIS strictness: bisect_left gives strictly increasing, bisect_right gives non-decreasing. Mixing them up fails on duplicates.
• Memory: an n x m table with n = m = 10^4 is 10^8 cells. If only the value is needed, keep two rows.

Interview variations

• Grid paths: minimum path sum, number of unique paths, paths with obstacles; same cell-by-cell fill.
• Longest common substring: characters must be contiguous, so a mismatch resets to 0: f[i][j] = f[i-1][j-1] + 1 if equal, else 0.
• Shortest common supersequence: length n + m - LCS; rebuild it by walking the LCS table.
• Minimum deletions to make two strings equal: n + m - 2 * LCS.
• Longest palindromic subsequence: LCS of the string and its reverse (or interval DP).
• Nested envelopes / box stacking in 2D: sort by width ascending and height descending, then run a strict LIS on heights.
• Counting or weighting LIS: number of longest increasing subsequences, maximum-sum increasing subsequence; keep extra arrays in the O(n^2) loop.
• Mountain arrays: compute LIS ending at each index from the left and from the right, then combine.