Skip to content

Volume ITechnology

4.23.0 — 1-D Dynamic Programming: The Pattern ​

Recognition cue. The answer is a count, a best value, or a yes/no, and the state can be described by one number — usually a position in an array or string, or a remaining budget.

How to tell it is DP and not greedy: a choice made now restricts the choices available later. Greedy cannot see that. DP handles it by remembering the consequence.

If you are unsure, 4.22 section 2 has the full decision. The short version: spend thirty seconds hunting a counterexample to the greedy rule. If you find one, it is DP. If you cannot find one and cannot prove the rule either, write the DP — it is never wrong, only slower.

The question that produces the recurrence ​

For a 1-D DP, one question does almost all the work:

How did I get here?

List the ways to arrive at state i. They must be disjoint and must cover everything. Then combine them:

the problem askscombine with
how many ways+
fewest / cheapestmin
best / largestmax
is it possibleor

Climbing Stairs and Min Cost Climbing Stairs have the same two arrival routes and differ only in that operator.

The five questions, in order ​

  1. What is the state? Say dp[i] in one English sentence. If you cannot, stop — nothing after this will work.
  2. What are the choices at each state? Usually two or three.
  3. What is the recurrence? Combine the choices with the right operator.
  4. What are the base cases? Check them by hand on the smallest input. Most wrong DP solutions have a correct recurrence and a wrong base.
  5. What order fills the table? Everything a cell reads must already be filled.

The state definition traps ​

"ending at i" versus "considering the first i". These are different states and they lead to different code.

  • Longest Increasing Subsequence needs ending at i, because you must know the last element to extend it. The answer is then max(dp), not dp[n-1].
  • House Robber uses considering the first i, so the answer is dp[n] directly.

Getting this backwards produces code that is nearly right and fails on half the tests. Say which one you are using out loud before writing anything.

The loop direction, which is not a detail ​

When a 1-D array is updated in place, the direction decides whether an item can be reused:

python
# each item used ONCE  → count DOWN
for item in items:
    for t in range(target, item - 1, -1):
        dp[t] = dp[t] or dp[t - item]

# items REUSABLE       → count UP
for item in items:
    for t in range(item, target + 1):
        dp[t] = dp[t] or dp[t - item]

Line by line. In both loops, dp[t] means "the total t can be made". For each item, we update every total that the item could help make: t can be made if it already could, or if t − item could and we add the item. The only difference is the direction of the inner loop. Counting down means dp[t - item] has not yet been touched for this item, so the item is used at most once. Counting up means dp[t - item] may already include this item, so it can be used again and again.

Going down, dp[t - item] still holds the value from before this item. Going up, it may already include it.

Partition Equal Subset Sum counts down. Coin Change counts up. That is the only structural difference between them.

The twelve problems ​

#ProblemThe one insight
4.23.1Climbing Stairs ★Fibonacci — arrive from one below or two
4.23.2Min Cost Climbing StairsThe same, with min instead of +
4.23.3House Robber ★Take it or leave it; taking forces a skip
4.23.4House Robber II ★Split the circle into two lines
4.23.5Longest Palindromic Substring ★Expand from 2n − 1 centres, not DP
4.23.6Palindromic Substrings ★Every expansion step is one more palindrome
4.23.7Decode Ways ★The two-step recurrence with validity rules
4.23.8Coin Change ★Try every coin as the last one
4.23.9Maximum Product Subarray ★Carry the minimum too — a negative flips it
4.23.10Word Break ★Where does the last word start?
4.23.11Longest Increasing Subsequence ★tails holds best endings, not a subsequence
4.23.12Partition Equal Subset Sum0/1 knapsack — count the loop down

★ marks the Blind 75 subset.

The traps on this pattern ​

A wrong base case. Check the smallest input by hand. dp[0] = 1 for counting problems (the empty way) and dp[0] = 0 for cost problems.

Answering with dp[n-1] when the state is "ending at i". Take the maximum over the table.

Updating two rolling variables in the wrong order. Compute both from the same snapshot, or use simultaneous assignment.

The loop direction on an in-place array. Down for once, up for reusable.

Reaching for greedy without a proof. If you cannot prove it, write the DP.

What the interviewer will push on ​

"What does dp[i] mean?" In one English sentence, before any code.

"Why is this not greedy?" Give a counterexample. Volunteering it is stronger than being asked.

"Why does the loop run that direction?" Reuse or no reuse.

"Can you reduce the space?" Name which cells the recurrence reads and keep only those. Then note that reconstructing the actual answer needs the full table, which is what the space optimisation gives up.

"Can you do better than O(n^2)?" Sometimes — LIS drops to O(n \log n); palindromes drop to O(n) with Manacher's.

One thing to volunteer: state the state definition, the base cases and the fill order before writing a line of code. That is the whole method, and doing it out loud converts a hard problem into a mechanical one.

Recall

  • 1-D DP when the state is one number and the answer is a count, an optimum, or a yes/no.
  • How to tell DP from greedy: a choice now restricts choices later. Test greedy by hunting for a counterexample for thirty seconds.
  • "How did I get here?" produces the recurrence. Combine with + for counting, min/max for optimising, or for possibility.
  • "Ending at i" versus "considering the first i" are different states — LIS needs the first and answers with max(dp); House Robber uses the second.
  • Loop direction on a rolled array decides reuse. Down = each item once (0/1 knapsack). Up = reusable (Coin Change).
  • Most wrong DP has a correct recurrence and a wrong base case — check the smallest input by hand.
  • Space optimisation costs you the ability to reconstruct the answer; keep the table if you need the choices.
  • Not everything filed under DP should be DP — palindromes are better by centre expansion.

Next: 4.23.1 Climbing Stairs — the smallest complete DP, shown in all four forms.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet