DP Thinking Framework

Dynamic Programming (DP) is about solving big problems by combining solutions to smaller subproblems with overlap. It sounds abstract, but in practice you can follow a concrete checklist.

This article gives you a repeatable framework for designing DP solutions instead of “hoping” a state appears.

Step 1: Identify Overlapping Subproblems

Common signs that DP may be appropriate:

  • Naive recursion revisits the same subproblem many times.
  • The problem asks for an optimal value (min/max) or count of ways.
  • Subproblems can be defined on prefixes, ranges, or smaller parameters:
    • f(i) – best answer for prefix [0..i].
    • f(i, j) – answer for substring / subarray between i and j.
    • f(i, cap) – best value using first i items and capacity cap.

Once you can express the problem in terms of smaller versions of itself, you’re halfway there.

Step 2: Define the State

The most important question:

What minimal information do I need to remember so that I can build the answer step by step?

Examples:

  • Longest Increasing Subsequence:
    • dp[i] = length of LIS ending at index i.
  • 0/1 Knapsack:
    • dp[i][w] = best value using first i items with capacity w.
  • Edit Distance:
    • dp[i][j] = min edits to convert s[0..i) to t[0..j).

Rule of thumb:

  • Include enough to make the transition local.
  • Exclude everything else (otherwise state blows up).

Step 3: Write the Transition

Once state is defined, ask:

How can I compute dp[state] using smaller states?

Classic patterns:

  • Choice‑based (pick or skip, take left/right, etc.):

    Java
    dp[i] = max(
    dp[i - 1],               // skip
    value[i] + dp[i - 2]     // take
);

  • Partition‑based (split at k):

    Java
    dp[i] = min over k < i of (dp[k] + cost(k, i));

  • 2D transitions (grids / strings):

    Java
    dp[i][j] = min(
    dp[i - 1][j] + costDelete,
    dp[i][j - 1] + costInsert,
    dp[i - 1][j - 1] + costReplaceOrMatch
);

If you can’t express a transition, your state is probably wrong or incomplete.

Step 4: Base Cases and Initialization

DP needs starting points:

  • For 1D:
    • dp[0] or dp[1] often comes from trivial cases (empty prefix, first element).
  • For 2D:
    • First row / column corresponds to aligning with empty string or zero length.

Always sanity check base cases on small inputs by hand.

Step 5: Evaluation Order (Top‑Down vs Bottom‑Up)

Two ways to compute DP:

  • Top‑down (memoized recursion):
    • Implement f(state) recursively.
    • Cache results in a map/array to avoid recomputation.
    • Easy to write, close to the mathematical definition.
  • Bottom‑up (iterative):
    • Order states so that dependencies are computed before uses.
    • Fill the dp table in loops.
    • Often more space‑efficient and avoids recursion limits.

In interviews, start with whichever is clearer to you, then optimize later if needed.

Step 6: Optimize Space When Possible

Many DP transitions only depend on:

  • Previous row / column.
  • A fixed‑size window of previous states.

In such cases, you can reduce space:

  • From O(n^2) to O(n) by keeping only current and previous row.
  • From O(n) to O(1) by keeping a few scalars.

Always ensure you don’t overwrite values you still need.

Common DP Pitfalls

  • State explosion: defining too much in the state (e.g. include whole subsets).
  • Incorrect transitions: missing choices or double‑counting.
  • Wrong iteration order in bottom‑up implementations.
  • Forgetting modulo for counting problems.

When unsure, print a small DP table for tiny inputs and inspect it manually.

Practice Strategy

To internalize the DP mindset:

  1. Solve multiple problems from each family:
    • 1D DP (stairs, house robber, simple knapsack).
    • 2D DP on strings (LCS, edit distance).
    • Interval DP / partition DP.
  2. For each, explicitly document:
    • State definition.
    • Transition formula.
    • Base cases.
    • Evaluation order.

Over time, you’ll find that new DP problems are often small twists on a familiar pattern, not completely new inventions.