Dynamic programming (1-D)

O(states)

Fill a row of boxes dp[i], where each box is worked out from a couple of earlier boxes by one rule, the recurrence. Scanning left to right once turns an exponential brute force into a single O(n) pass.

Signals

best/maximum/minimum ending at position iways to reach, climb, or tilecannot pick two adjacent itemsminimum cost path through a gridoverlapping subproblems, same state recomputed

Template

function maxSubarraySum(nums) {
    let best = nums[0];
    let curr = nums[0];
    for (let i = 1; i < nums.length; i++) {
        curr = Math.max(nums[i], curr + nums[i]);
        best = Math.max(best, curr);
    }
    return best;
}

Looks similar, isn't

Greedy: Greedy locks in whichever choice looks best right now and never revisits it, which only works when you can prove that local choice is always safe with an exchange argument. Most counting or optimization problems with a state that overlaps across choices need the full dp table instead, because the locally best pick can block a better global answer.
Memoization: Memoization is the same recurrence written top-down: a plain recursive function plus a cache for states it has already solved. Bottom-up DP fills the table in a fixed order instead, which avoids recursion depth limits and lets you drop old rows once nothing later needs them.

n up to 1e5..1e6, one left-to-right pass filling dp[i] from a couple earlier boxes -> O(n): each state computed once in O(1).

Learn this pattern