Topic 17 of 20
Dynamic Programming – 1D
Recursion plus memory: define a state, write the recurrence, fill the table.
The concept
Dynamic programming (DP) solves problems made of overlapping subproblems by solving each subproblem once and storing the answer. If your backtracking solution keeps recomputing the same calls, DP is the fix. A DP solution has three parts: a state (what does dp[i] mean, in one precise sentence?), a recurrence (how is dp[i] built from smaller states?), and base cases.
There are two ways to implement it. Top-down (memoisation) is your recursive solution plus a cache, and it is usually the easiest place to start. Bottom-up (tabulation) fills an array in order. It avoids recursion limits and often lets you shrink memory to a few variables. In interviews, starting top-down and then converting to bottom-up is a strong way to show understanding.
In 1D DP the state is a single index or amount. Learn the families here (Fibonacci-style steps, take-or-skip, 0/1 and unbounded knapsack, longest increasing subsequence, segmentation) and most new DP problems will turn out to be one of them in disguise.
Patterns you will learn
Problems, in order
- 1Climbing StairsEasy
The 'hello world' of DP.
Fibonacci-style RecurrenceReported at: AmazonMicrosoftGoogle+4 - 2
Adds costs to the stair recurrence.
Fibonacci-style RecurrenceReported at: AmazonAdobeBloomberg - 3
Rolling variables for O(1) space.
Fibonacci-style RecurrenceReported at: Amazon - 4
Building each row from the previous one.
Row-by-row ConstructionReported at: AmazonAppleMicrosoft+3 - 5House RobberMedium
The canonical take-or-skip recurrence.
Take / Skip (House Robber)Reported at: AmazonAppleGoogle+6 - 6House Robber IIMedium
Handle a circle by solving two linear cases.
Take / Skip (Circular)Reported at: GoogleAmazon - 7Delete and EarnMedium
Reduces to House Robber after bucketing values.
Take / Skip (House Robber)Reported at: AmazonGoogleGoldman Sachs - 8Decode WaysMedium
Counting decodings with validity checks; asked often at Meta.
Fibonacci-style RecurrenceReported at: AmazonGoogleMeta+5 - 9Coin ChangeMedium
Minimum coins, the classic unbounded knapsack.
Unbounded KnapsackReported at: AmazonMicrosoftGoogle+3 - 10
- 11Combination Sum IVMedium
Counting ordered sequences; contrast it with Coin Change II.
Unbounded Knapsack (Permutations)Reported at: AmazonGoogleMeta+1 - 12Perfect SquaresMedium
Minimum squares, with a BFS alternative.
Unbounded KnapsackReported at: GoogleAmazonApple+1 - 13
Subset sum with a boolean 0/1 knapsack.
0/1 KnapsackReported at: MetaMicrosoftAmazon+3 - 14Target SumMedium
Reducing ± signs to a subset-sum count.
0/1 Knapsack (Counting)Reported at: MetaAmazonGoogle+2 - 15
- 16Maximum Product SubarrayMedium
Track both max and min because negatives flip signs.
Kadane VariantsReported at: AmazonMicrosoftGoogle+4 - 17
Circular max = total − minimum subarray.
Kadane VariantsReported at: AmazonGoogle - 18Word BreakMedium
Segmentation DP; one of the most-asked DP problems.
Word Break / SegmentationReported at: AmazonMetaApple+5 - 19
O(n²) DP and the O(n log n) patience-sorting method.
- 20
Expand around centres, or interval DP.
Palindromic Substrings (Expand)Reported at: AmazonMicrosoftGoogle+6 - 21Palindromic SubstringsMedium
Counting all palindromic substrings.
Palindromic Substrings (Expand)Reported at: MetaX (Twitter) - 22Word Break IIHard
Memoised enumeration of all segmentations.
Word Break + BacktrackingReported at: MetaAmazonApple+5 - 23
Sort cleverly, then run LIS.
Longest Increasing Subsequence (2D)Reported at: GoogleByteDance / TikTok - 24
Weighted interval scheduling; asked frequently at Google and Amazon.
- 25Frog JumpHard
State design with a hash map of reachable jumps.
DP over (Position, Last Jump)Reported at: AmazonMicrosoftGoogle+1