Dynamic programming in 1D

Forty days of offers, and a script that never finished

A marketing team wants to send one cashback offer a day for the 40 days before a festival. Each day has a predicted value in rupees, and there is one rule: never two days in a row, because people who get offers on consecutive days mute the app.

The obvious planner is a recursion. best(day) is the most value you can get from the days up to and including that day. It compares two plans: skip the day, which gives best(day - 1), or send on it, which adds the day's value to best(day - 2), because the day before must then be left empty. On a 10-day test it answers at once. On the real 40 days it is still running after ten minutes.

Add a counter and run the 30-day version, which does finish: 2,692,537 calls. For 40 days the same recursion makes 331,160,281. Now count the different questions it can ask: best(0), best(1), and so on up to best(40), which is 41 questions. The recursion makes over 300 million calls to answer those 41 questions, so it computes the same answers again and again. The answer for day 17, for example, is the same whichever branch of the recursion asks for it.

Pause and predict What is the smallest change that makes the planner finish in a blink?

Answer each prefix once

The planner is the same problem as House Robber, a standard interview problem: houses stand in a row, you may not rob two neighbours, and you want the most money. Start with a simpler problem of the same shape. A staircase has n steps, and each move climbs 1 or 2 steps. How many different sequences of moves reach the top? Look at the last move. It was either a 1-step from step n - 1 or a 2-step from step n - 2. So the count for n is the count for n - 1 plus the count for n - 2.

That sentence describes a recursion. Written as plain recursion, it is backtracking: it walks through every sequence of moves one by one.

Pause and predict Plain recursion for n = 30. How many calls does it make?

The method, in four questions

Every DP is built by answering the same four questions. Answer them in order, in words, before any code.

1. What does dp[i] mean? Say it in words, for example "the number of ways to reach step i" or "the most money from the first i houses". If you cannot say it in one sentence, you do not have a DP yet.
2. How is dp[i] built from smaller cells? This rule is called the transition. To find it, ask what the last choice in any solution for the first i items could be. Each possible last choice leaves a shorter prefix behind, and the definition tells you which cell holds the answer for that prefix.
3. Which cells are the base? These are the cells the transition cannot build, usually the empty prefix, dp[0]. Ask what the definition says about zero items.
4. In what order are the cells filled? Any order works if every cell is filled after the cells it reads. For prefixes, that means left to right.

Then write it three times, in this order: the memo (the recursion, with answers stored), the table (the same thing as a loop), and the rolling variables (only the cells the transition still needs).

Why a greedy fails here

Back to House Robber: houses stand in a row, you may never rob two neighbours, and you want the most money. A greedy algorithm makes one choice at each step and never revisits it. In this problem, each choice changes which houses are allowed next, so an early choice can rule out a better plan.

Pause and predict Take this greedy rule: rob the biggest house that is still allowed, rule out its two neighbours, and repeat. On nums = [3, 4, 3], how much money does it take?

DP or backtracking?

Both start from the same recursion. Backtracking walks every path through it, which is right when the answer is the list of paths ("every way to cut the string"). DP collapses paths that lead to the same question, which is right when the answer is a number or a yes or no ("how many ways", "the least cost", "can it be cut"). To decide between them, ask whether the answer for a prefix depends on how you reached it. If it does not, store the answer and reuse it.

The same move turns up elsewhere. Counting the calls before running anything, as the opening example did, is a back-of-envelope estimate: numbers that change decisions. And an LLM stores each token's keys and values instead of recomputing them for every new word, which is a memo over positions: the KV cache.

How to recognise it

The statement asks for a count, a minimum or maximum, or a yes or no. At each index there is a small choice, and that choice affects only the next index or two. To check, ask yourself: "If I knew the answer for every shorter prefix, could I work out this one?"

Pause and predict Which of these is a 1D DP over prefixes?

Four that only look like it

• A choice you never need to undo. In Jump Game you track the farthest index you can reach, and in Kadane's algorithm the best sum ending here. Each is a greedy with a proof that it is correct. Look for a small counterexample first; if you find one, you need DP.
• A request to list every subset, cut or arrangement. The output can be exponentially long, so the problem is backtracking, sometimes sped up by a DP table that rules out dead ends.
• A capacity or a target sum as well as an index. For "can these numbers make 11?", the state must also hold the amount still needed. That is knapsack.
• Two strings or a grid. The state is two prefixes at once, one for each string or one for each axis. That is DP on grids and strings.

Where it bites

Pause and predict A Java memo for House Robber is an int array left at 0, and 0 means 'not computed'. On twenty houses that are all worth 0, how many calls does it make?

• Writing code before dp[i] has a definition in words. Most wrong transitions come from a definition that was never stated.
• Getting the empty-prefix base wrong. dp[0] is 1 in Decode Ways and Climbing Stairs, and true in Word Break. If it is 0 or false, every cell built from it is 0 or false too.
• Being off by one between dp and the input. When dp is indexed by prefix length, the last item in the first i items is nums[i - 1]. The table has n + 1 cells, and the answer is dp[n].
• Running one House Robber pass on a circle. On a circle, the first and last houses are neighbours, and a single pass over the row can rob both. Run it twice, once without the first house and once without the last.
• Keeping one value when the problem needs two. For products, keep both the largest and the smallest product ending here, and compute both new values from the old ones.
• Trusting a greedy rule without testing it. Try it by hand on three or four small inputs before you commit to it.