parikshan

1-D Dynamic Programming

The core idea

Dynamic programming is recursion plus memory. You define a function dp(i) that returns the answer for the subproblem ending at index i, write a recurrence that expresses dp(i) in terms of dp(i-1), dp(i-2), ..., and either memoise top-down or build bottom-up.

The whole skill is writing the recurrence. Once you have it, the implementation is mechanical.

1-D DP means the state is one number (the index, or the remaining capacity, or the current sum). The table has n entries.

The four DP questions, in order:

  1. What is the state? (One sentence: "dp(i) is the answer for the prefix [0..i]".)
  2. What is the base case? (dp(0) or dp(-1) or both.)
  3. What is the transition? (dp(i) in terms of smaller dp's.)
  4. What is the final answer? (dp(n-1), or max over dp(i), or dp(n-1) + something.)

When to reach for it

Trigger phrases:

  • "in how many ways can you ..."
  • "minimum / maximum cost to ..."
  • "longest / shortest ... satisfying ..."
  • the answer depends on choices made earlier
  • greedy obviously fails (pick the smallest example where it does)

If the problem asks for a count, sum, min, or max over decisions, and you cannot greedily commit at each step, DP is the tool.

How to approach

  1. Solve the smallest non-trivial case (n=1, n=2, n=3) by hand. Look for a pattern.
  2. Define dp(i) precisely. Most bugs come from a fuzzy definition.
  3. Write the recurrence with concrete examples ("dp(3) = max(dp(1) + cost[3], dp(2))"). Verify against the cases you solved by hand.
  4. Decide direction (top-down with memo, or bottom-up with an array). For 1-D DP, bottom-up is usually cleaner.
  5. Notice if only the last one or two states are needed; collapse the array into two variables for O(1) space.

Real-world applications

  • Pricing: optimal pricing over time with capacity constraints.
  • Speech recognition: the Viterbi algorithm is DP over hidden states.
  • Bio-informatics: sequence alignment.
  • Scheduling: weighted-interval scheduling.
  • Financial planning: optimal savings / withdrawals.
  • Inventory: when to reorder, how much.
  • NLP: tokenisation, segmentation.

In the AI-integrated workspace

DP is where agents most often write code that looks right but solves the wrong problem. Because the recurrence is the entire idea, getting it slightly wrong (off-by-one in a transition, wrong base case) produces code that compiles, runs, and returns plausible-looking answers that are simply incorrect. Tests on the sample input often pass.

Code-review demand: ask the agent to write the recurrence as a comment above the loop. If the comment is missing or vague, the code is unreliable. If the comment is precise, you can verify it on a small case in your head.

The second failure: agents picking memoised recursion when bottom-up would have been linear, then blowing the recursion limit on a 10⁵-element input. For 1-D DP, prefer bottom-up.

In an AI-assisted workflow, DP is also the place where you most often want to draw the table with the agent. Spreadsheet-style: rows are i, columns are state, cells are values. If the agent's code disagrees with the table on row 3, the code is wrong.

Problems in this cluster

Easy: climbing-stairs, min-cost-climbing-stairs. Medium: house-robber, maximum-subarray, maximum-product-subarray, jump-game, jump-game-ii, coin-change, longest-increasing-subsequence, longest-palindromic-substring.

Start with climbing-stairs. The deep article walks the recurrence from scratch and is the template for every later DP article.