1-D Dynamic Programming

12 questions. Every one is the same pipeline; what varies is the recurrence, the combiner, and whether the state can be compressed.

The two properties that license DP

The same subproblem, computed again and again

Optimal substructure — the answer is built from answers to smaller inputs
Overlapping subproblems — the same smaller input recurs

Without (2) it's plain divide and conquer and caching buys nothing. The signal is exponentially many calls over polynomially many distinct inputs.

The four stages

Every DP solution is the same four stages

Write the recursion first — it's obviously correct. Then memoise, tabulate, and roll. Each step is mechanical once the recurrence exists.

The combiner is chosen by the question

The structure comes from the allowed moves; the combiner comes from what's being asked. They're independent choices.

Goal	Combiner	Questions
count the ways	`+`	1, 7
best / cheapest	`min` / `max`	2, 3, 4, 8, 9, 11, 12
does one exist	`\|\|`	10, 12

Min Cost Climbing Stairs is Climbing Stairs with min for + — same recurrence, one substitution.

When you CAN roll to `O(1)` space

Only when the recurrence reads a fixed window of previous cells.

Recurrence	Rolls?	Questions
`dp[i] = f(dp[i-1], dp[i-2])`	yes — two variables	1, 2, 3, 4, 7, 9
`dp[i] = f(dp[j])` for a range of `j`	no — array required	8, 10, 11, 12

Word Break, Coin Change and LIS are the counterexamples: each reads many earlier cells, so nothing can be discarded.

Ascending vs descending — knapsack's whole distinction

Loop direction	Meaning	Question
ascending	an item may be reused — unbounded knapsack	8 (Coin Change)
descending	each item used once — 0/1 knapsack	12 (Partition Equal Subset Sum)

Descending means dp[s - n] still holds the value from before this item was considered. Verified: the ascending variant of question 12 disagreed with the correct answer on 44 of 400 random inputs.

Easy Climbing Stairs LC 70 11 min Easy Min Cost Climbing Stairs LC 746 9 min Medium House Robber LC 198 10 min Medium House Robber II LC 213 10 min Medium Longest Palindromic Substring LC 5 12 min Medium Palindromic Substrings LC 647 9 min Medium Decode Ways LC 91 11 min Medium Coin Change LC 322 12 min Medium Maximum Product Subarray LC 152 11 min Medium Word Break LC 139 12 min Medium Longest Increasing Subsequence LC 300 12 min Medium Partition Equal Subset Sum LC 416 12 min

Where DP is NOT the best answer

Question 5. The isPal[i][j] table is O(n²) time and space; expand-around-centre is O(n²) time and O(1) space. The table earns its place only when queried repeatedly — which is Palindrome Partitioning, not this.

LIS: the reframe that changes what's indexed

tails holds the smallest tail for each length

The O(n²) DP indexes by position. The patience method indexes by length — tails[k] is the smallest tail of any increasing subsequence of length k+1. That array is sorted by construction, so the scan becomes a binary search.

tails is not the answer subsequence. On the example it ends as [2,3,7,18], but 18 comes after 101 in the input. Only its length is meaningful.

The traps

Trap	Symptom
`memo[n] != 0` when 0 is a valid answer (Q1)	Infinite recomputation
Returning `dp[n-1]` instead of `dp[n]` (Q2)	Answers a different question
`dp[1] = nums[1]` instead of `max` (Q3)	`[5,1]` returns 1
Forgetting the circular case split (Q4)	`[5,1,1,5]` returns 10 instead of 6
Only odd-length centres (Q5, Q6)	`"cbbd"` misses `"bb"`
Missing the leading-zero guard (Q7)	`"06"` returns 1 instead of 0
`two <= 26` without `>= 10` (Q7)	`"06"` counted as F
`Integer.MAX_VALUE` sentinel (Q8)	Overflows to `MIN_VALUE`; wins every `min`
Greedy coin selection (Q8)	`[1,3,4]` amount 6 gives 3, not 2
Not snapshotting the old max (Q9)	`[-1,-2,-3]` returns 12 — an impossible value
`boolean[]` memo when false is an answer (Q10)	Recomputes every false
`dp[n-1]` instead of `max(dp)` (Q11)	`[1,2,3,0]` returns 1
Missing the odd-total check (Q12)	`[1,2,3,5]` returns true
Ascending loop in 0/1 knapsack (Q12)	Items reused

Sentinels need a domain check

Three questions overload a value to mean "not computed" or "unreachable", and each works only because the sentinel is provably outside the answer range:

Question	Sentinel	Safe because
Climbing Stairs	`0`	The count is always `>= 1`
Coin Change	`amount + 1`	Worst case is `amount` coins — and it survives `+ 1`
Word Break	`null` (`Boolean[]`)	`false` is a legitimate answer

Integer.MAX_VALUE fails the Coin Change case precisely because the recurrence adds to it.

Verification

Every snippet compiled and cross-checked against an independent implementation — 4,000+ randomized cases:

Q1–Q3, Q7, Q10, Q12 against their own exponential recursions
Q4 against circular subset enumeration with a wraparound adjacency check
Q5, Q6, Q9 against all-substrings / all-subarrays brute force
Q6's run-of-k formula k(k+1)/2 verified independently at k = 100
Q11 across both the O(n²) and O(n log n) implementations

Five deliberately-broken variants confirm the traps:

omitting Q7's leading-zero guard returns 1 for "06"
greedy on [1,3,4] with amount 6 gives 3 where the DP gives 2
omitting Q9's max snapshot returns 12 for [-1,-2,-3] — a value no subarray achieves
omitting Q12's odd-total check returns true for [1,2,3,5]
Q12's ascending loop disagreed on 44 of 400 random inputs