What this module covers: Module P-11 covered the mechanics — memoization and tabulation are close to mechanical once you know the recurrence. The actual skill in dynamic programming is figuring out what table[i] should represent in the first place. This module works through three classic problems where that state definition is the real challenge, each with a different shape of recurrence.
The Real Question: What Does dp[i] Mean?
Every 1D DP problem starts with the same question: if dp[i] holds "the answer to this problem, restricted to just the first i elements," what's the relationship between dp[i] and the smaller answers before it? Get that relationship right, and the rest — memoization or tabulation — is mechanical, exactly as Module P-11 showed.
House Robber: Choose or Skip
You're robbing houses along a street; adjacent houses can't both be robbed (the alarm links them). Maximize total loot.
typescript
The state definition is: dp[i] = best possible loot using only houses 0 through i. The recurrence falls directly out of the problem's one constraint — you can't rob two adjacent houses, so robbing house i forces you to have skipped house i - 1, meaning the best you can add to is dp[i - 2], not dp[i - 1]. Skipping house i entirely just carries forward whatever dp[i - 1] already was. This is the same "only look back a fixed number of steps" shape as Module P-11's Fibonacci, so the same O(1)-space trick applies — only dp[i-1] and dp[i-2] are ever needed.
Coin Change: Minimum Coins to Reach an Amount
Given coin denominations and a target amount, find the minimum number of coins needed (or determine it's impossible).
typescript
Here dp[a] = the minimum coins needed to make amount a exactly. For each amount, the recurrence tries every coin denomination: if you use one coin of value coin, the remaining amount to cover is a - coin, which has already been solved (it's smaller, and the loop processes amounts in increasing order) — so dp[a - coin] + 1 is a candidate answer, and you take the minimum across all coins tried. This is a genuinely different recurrence shape from House Robber: instead of only ever looking back 1 or 2 fixed steps, it looks back by a variable amount (coin, for each denomination), which is exactly why this can't be compressed to O(1) space the way Fibonacci and House Robber could — every entry in dp might still be needed by some later amount, depending on the coin denominations available.
Decode Ways: Counting Ambiguous Interpretations
A string of digits was encoded by mapping 'A' → 1, 'B' → 2, ... 'Z' → 26. Given the encoded digit string, count how many different letter sequences could have produced it — the ambiguity being that a two-digit chunk like "12" could be read as either "1" "2" (A, B) or "12" (L).
typescript
dp[i] = the number of valid decodings of the first i characters. The recurrence checks two independent possibilities at each step — does the last single character stand alone as a valid letter, and does the last two characters together stand alone as a valid letter — and adds both contributions together, because they represent genuinely different, non-overlapping ways of reaching the same prefix length. This "add contributions from multiple valid predecessor states, not just pick the max of one" shape is different again from both House Robber (pick the max of exactly two choices) and Coin Change (pick the min across several choices) — worth noticing, because recognizing which combination rule applies (max, min, sum) is as much a part of "defining the state" as choosing what dp[i] represents in the first place.
Where This Shows Up in Your Stack
House Robber's "non-adjacent selection, maximize value" shape models real scheduling problems directly — choosing a maximal set of non-overlapping ad slots, meeting bookings, or shifts from a linear timeline where adjacent options conflict is structurally the same recurrence.
Coin Change's "minimum units to reach a target" shape generalizes to resource allocation with fixed denominations — packing shipments into a minimum number of container sizes, or provisioning a minimum number of server instance types to meet a capacity target, when instance sizes come in fixed increments rather than continuously.
Decode Ways' ambiguous-parse-counting shape appears in real parsing problems — counting (or enumerating) valid ways to tokenize an ambiguous input format, where a chunk of characters could plausibly be read as one token or split into two, is exactly this recurrence, generalized beyond digit-to-letter decoding.
Summary
The core skill in 1D DP is defining what dp[i] represents — everything else follows from getting that state definition right.
House Robber: dp[i] = max loot using houses 0..i; recurrence picks the max of "skip" (dp[i-1]) vs. "rob" (dp[i-2] + nums[i]) — a fixed, two-step lookback, compressible to O(1) space.
Coin Change: dp[a] = min coins to make amount a; recurrence tries every coin denomination and takes the minimum — a variable-distance lookback that generally can't be compressed below O(amount) space.
Decode Ways: dp[i] = number of ways to decode the first i characters; recurrence sums two independent valid-predecessor contributions (one-digit and two-digit), rather than picking a max or min.
Recognizing which combination rule applies — max (House Robber), min (Coin Change), or sum (Decode Ways) — is as central to solving a DP problem as identifying the state itself.
The next module, Dynamic Programming III: 2D DP and Knapsack, extends this from a single dimension (position i in a sequence) to two — where the state depends on both a position and a resource constraint, like remaining capacity.
Knowledge Check
In rob, why does the recurrence for dp[i] use dp[i - 2] + nums[i] (skipping two positions back) when choosing to rob house i, rather than dp[i - 1] + nums[i]?
Why can't coinChange's space be compressed to O(1) the way rob's (or Module P-11's Fibonacci's) could be, according to the module's reasoning?
In numDecodings, why does the recurrence use dp[i] += dp[i - 1] and dp[i] += dp[i - 2] (adding both contributions together), rather than taking the maximum of the two, as rob does?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
functionrob(nums:number[]):number{if(nums.length ===0)return0;if(nums.length ===1)return nums[0];// dp[i] = the maximum loot achievable considering houses 0..iconst dp =newArray(nums.length); dp[0]= nums[0]; dp[1]= Math.max(nums[0], nums[1]);for(let i =2; i < nums.length; i++){// At house i, you have exactly two choices: dp[i]= Math.max( dp[i -1],// skip house i — carry forward the best result without it dp[i -2]+ nums[i]// rob house i — add its value to the best result two houses back);}return dp[nums.length -1];}
functioncoinChange(coins:number[], amount:number):number{// dp[a] = minimum coins needed to make exactly amount `a`; Infinity means "not yet known to be possible"const dp =newArray(amount +1).fill(Infinity); dp[0]=0;// zero coins needed to make amount 0for(let a =1; a <= amount; a++){for(const coin of coins){if(coin <= a && dp[a - coin]!==Infinity){ dp[a]= Math.min(dp[a], dp[a - coin]+1);// use one of this coin, plus however many coins made the rest}}}return dp[amount]===Infinity?-1: dp[amount];}coinChange([1,5,10,25],30);// 2 — a 25 and a 5
functionnumDecodings(s:string):number{const n = s.length;if(n ===0|| s[0]==='0')return0;// a leading zero can never be validly decoded// dp[i] = number of ways to decode the first i characters of the stringconst dp =newArray(n +1).fill(0); dp[0]=1;// one way to decode an empty prefix — the "do nothing" case dp[1]=1;// s[0] is already confirmed non-zero abovefor(let i =2; i <= n; i++){const oneDigit =Number(s[i -1]);// the single most recent character, as its own letterconst twoDigit =Number(s.slice(i -2, i));// the most recent two characters, as one letterif(oneDigit >=1&& oneDigit <=9){ dp[i]+= dp[i -1];// valid as a standalone digit — carries forward all ways to decode everything before it}if(twoDigit >=10&& twoDigit <=26){ dp[i]+= dp[i -2];// also valid as a two-digit pair — carries forward all ways to decode everything before THAT}}return dp[n];}numDecodings('226');// 3 — "BBF" (2,2,6), "BZ" (2,26), "VF" (22,6)