What is dynamic programming?

DP is not a specific algorithm; it is a way of organising a solution. You define a state that captures everything needed to describe a subproblem, write a recurrence that relates that state to smaller states, and compute states in an order that makes the answers available.

The two ingredients

• Overlapping subproblems: the same state is needed more than once
• Optimal substructure: the best answer can be built from best answers to subproblems
• State: the minimum information that separates one subproblem from another
• Transition: how a state is computed from smaller states
• Base cases: the smallest states that can be answered directly

function climbStairs(n) {
  if (n <= 2) return n;
  let prev = 1;
  let current = 2;
  for (let step = 3; step <= n; step++) {
    const next = prev + current;
    prev = current;
    current = next;
  }
  return current;
}

Start by writing the recurrence and the base cases before optimising memory. Once the table is correct, you can often reduce it to a few rolling variables. That order avoids clever but incorrect code.