The shape of the problem
Linear dynamic programming applies when the answer for position i can be built from a small number of previous positions. The classic example is climbing stairs: the number of ways to reach step i equals the ways to reach step i minus one plus the ways to reach step i minus two.
Building the table
- Define a state, often dp at i, that captures the answer for the prefix ending at i.
- Write a recurrence that expresses dp at i using earlier entries.
- Fill the array from left to right so dependencies are ready before they are needed.
A typical recurrence looks like dp at i equals some combination of dp at i minus one and dp at i minus two. House robber, maximum subarray, and decode ways all fit this mold with different combining rules.
Base cases and order
Set the first one or two entries directly, then iterate. Because each entry reads only a constant number of predecessors, the total work scales linearly with the input length.
Key idea
Linear DP walks a single array from left to right, computing each entry from a fixed window of earlier entries, turning an exponential recursion into a single fast pass.