Dynamic programming solves problems by breaking them into overlapping subproblems and storing the results so each subproblem is solved exactly once. In 1D DP, the state is a single variable - an amount, an index, or a position - and the dp array is one-dimensional. The coin change problem is the clearest introduction to this pattern because the recurrence is intuitive and the table-filling process is easy to visualize.

The Problem

Given a set of coin denominations and a target amount, find the minimum number of coins needed to make that amount. Each coin can be used an unlimited number of times. If the amount cannot be made, return -1.

This is an unbounded knapsack variant. Unlike the 0/1 knapsack where each item is used at most once, you can pick the same coin repeatedly. The "unbounded" property means the recurrence looks back at the same dp array row rather than a previous row.

Defining the State

Let dp[i] represent the fewest coins needed to make amount i. The base case is dp[0] = 0 because zero coins are needed for amount zero. Every other entry starts at infinity (or a value larger than any possible answer) to indicate "not yet achievable."

The recurrence for each amount i and each coin c is:

dp[i] = min(dp[i], dp[i - c] + 1)   for every coin c where c <= i

This says: to make amount i using coin c, you need one coin (the coin c itself) plus however many coins it takes to make the remaining amount i - c. You try every coin and keep the minimum.

Tracing Through an Example

Consider coins = [1, 5, 7] and amount = 11. Initialize dp[0] = 0, and dp[1] through dp[11] = infinity.

Building the table step by step:

• dp[1]: try coin 1 -> dp[1-1] + 1 = dp[0] + 1 = 1. Coins 5 and 7 are too large. dp[1] = 1.
• dp[2]: try coin 1 -> dp[1] + 1 = 2. dp[2] = 2.
• dp[3]: try coin 1 -> dp[2] + 1 = 3. dp[3] = 3.
• dp[4]: try coin 1 -> dp[3] + 1 = 4. dp[4] = 4.
• dp[5]: try coin 1 -> dp[4] + 1 = 5. Try coin 5 -> dp[0] + 1 = 1. dp[5] = 1.
• dp[6]: try coin 1 -> dp[5] + 1 = 2. Try coin 5 -> dp[1] + 1 = 2. dp[6] = 2.
• dp[7]: try coin 1 -> dp[6] + 1 = 3. Try coin 5 -> dp[2] + 1 = 3. Try coin 7 -> dp[0] + 1 = 1. dp[7] = 1.
• dp[8]: try coin 1 -> dp[7] + 1 = 2. Try coin 5 -> dp[3] + 1 = 4. Try coin 7 -> dp[1] + 1 = 2. dp[8] = 2.
• dp[9]: try coin 1 -> 3. Try coin 5 -> dp[4] + 1 = 5. Try coin 7 -> dp[2] + 1 = 3. dp[9] = 3.
• dp[10]: try coin 1 -> 4. Try coin 5 -> dp[5] + 1 = 2. Try coin 7 -> dp[3] + 1 = 4. dp[10] = 2.
• dp[11]: try coin 1 -> 3. Try coin 5 -> dp[6] + 1 = 3. Try coin 7 -> dp[4] + 1 = 5. dp[11] = 3.

The answer is dp[11] = 3, corresponding to coins 1 + 5 + 5, or 1 + 3 ones + 1 seven (but 1+5+5 uses fewer). The key observation is that a greedy approach (always pick the largest coin) would choose 7 + 1 + 1 + 1 + 1 = 5 coins. DP finds the true optimum because it explores all combinations implicitly through the recurrence.

The Code

Watch the DP table fill in step by step as each amount builds on previously solved subproblems:

Time complexity is O(amount * len(coins)). Space is O(amount) for the dp array.

Why This Is Unbounded Knapsack

In the standard 0/1 knapsack, each item can be used at most once, so dp[i] depends on dp values from the previous item's row - you need a 2D table (items by capacity). In unbounded knapsack, items are reusable, so dp[i] can reference dp[i - c] from the same computation pass. The coin change recurrence dp[i] = min(dp[i - c] + 1) looks back within the same array, which is why a 1D array suffices. This is the structural difference that makes coin change a 1D DP problem despite having two input dimensions (coins and amount).

Practice

The Longest Increasing Subsequence (LIS) is a foundational DP problem that introduces a different recurrence pattern from coin change. Instead of building up to a target value, you build up to each index, asking: what is the longest increasing subsequence that ends here? This "ending at index i" framing is the key insight.

The Problem

Given an array of integers, find the length of the longest subsequence where each element is strictly greater than the previous. A subsequence preserves relative order but does not need to be contiguous. For example, in [10, 9, 2, 5, 3, 7, 101, 18], the LIS is [2, 3, 7, 101] with length 4.

Defining the State

Let dp[i] be the length of the longest increasing subsequence ending at index i. Every element by itself is a subsequence of length 1, so dp[i] starts at 1 for all i.

The recurrence is: for each index j < i, if nums[j] < nums[i], then nums[i] can extend the subsequence ending at j. So:

dp[i] = max(dp[j] + 1)   for all j < i where nums[j] < nums[i]

The final answer is max(dp[0], dp[1], ..., dp[n-1]) because the longest subsequence could end at any index.

Tracing Through [10, 9, 2, 5, 3, 7, 101, 18]

Initialize dp = [1, 1, 1, 1, 1, 1, 1, 1].

• i=0 (value 10): no j < 0. dp[0] = 1.
• i=1 (value 9): check j=0 (10). 10 is not < 9. dp[1] = 1.
• i=2 (value 2): check j=0 (10), j=1 (9). Neither is < 2. dp[2] = 1.
• i=3 (value 5): check j=0 (10, no), j=1 (9, no), j=2 (2 < 5, yes). dp[3] = dp[2]+1 = 2.
• i=4 (value 3): check j=0 (10, no), j=1 (9, no), j=2 (2 < 3, yes), j=3 (5, no). dp[4] = dp[2]+1 = 2.
• i=5 (value 7): j=2 gives dp[2]+1=2, j=3 gives dp[3]+1=3, j=4 gives dp[4]+1=3. dp[5] = 3.
• i=6 (value 101): j=0 gives 2, j=1 gives 2, j=2 gives 2, j=3 gives 3, j=4 gives 3, j=5 gives 4. dp[6] = 4.
• i=7 (value 18): j=2 gives 2, j=3 gives 3, j=4 gives 3, j=5 gives 4. dp[7] = 4.

Final dp = [1, 1, 1, 2, 2, 3, 4, 4]. Answer = max(dp) = 4.

The Code

See how each element scans backward to find the longest chain it can extend:

Time is O(n^2) - for each of the n elements, you scan all previous elements. Space is O(n).

The O(n log n) Approach with Patience Sorting

The O(n^2) solution is the standard DP approach and what interviewers typically expect you to code first. But there is an O(n log n) algorithm worth understanding conceptually.

Maintain an array tails where tails[k] is the smallest possible tail element for an increasing subsequence of length k+1. For each new element x:

• If x is larger than all elements in tails, append it (extend the longest subsequence).
• Otherwise, find the smallest element in tails that is >= x (using binary search) and replace it with x.

The length of tails at the end is the LIS length. This works because replacing a tail with a smaller value never makes the current subsequences invalid - it only opens up more possibilities for future elements to extend them.

Practice

Word break introduces a different 1D DP flavor: instead of optimizing a numeric value, you are computing a boolean - can the string be segmented? The dp array holds true/false values, and the recurrence checks whether any split point produces two valid parts.

The Problem

Given a string s and a dictionary of words, determine if s can be segmented into a sequence of one or more dictionary words. Words can be reused. For example, "leetcode" with dictionary ["leet", "code"] returns true because "leet" + "code" covers the entire string.

Defining the State

Let dp[i] be true if the substring s[0:i] (the first i characters) can be segmented using dictionary words. The base case is dp[0] = true - the empty string is trivially segmentable.

The recurrence checks every possible split point j from 0 to i-1:

dp[i] = true   if any dp[j] is true AND s[j:i] is in the dictionary

In words: the first i characters are segmentable if there exists some split point j where the first j characters are segmentable AND the substring from j to i is a valid dictionary word.

Tracing Through "leetcode"

Dictionary = ["leet", "code"]. String = "leetcode" (length 8). Initialize dp[0] = true, dp[1..8] = false.

• dp[1]: check j=0, s[0:1]="l". "l" not in dict. dp[1] = false.
• dp[2]: check j=0, s[0:2]="le" (no). j=1, dp[1]=false (skip). dp[2] = false.
• dp[3]: check j=0, s[0:3]="lee" (no). j=1, dp[1]=false. j=2, dp[2]=false. dp[3] = false.
• dp[4]: check j=0, s[0:4]="leet" - yes, and dp[0]=true. dp[4] = true.
• dp[5]: check j=0, s[0:5]="leetc" (no). j=1 through j=3, dp is false. j=4, dp[4]=true, s[4:5]="c" (no). dp[5] = false.
• dp[6]: similar checks, nothing matches. dp[6] = false.
• dp[7]: similar checks, nothing matches. dp[7] = false.
• dp[8]: check j=0 through j=3 (dp all false or substring not in dict). j=4, dp[4]=true, s[4:8]="code" - yes! dp[8] = true.

The answer is dp[8] = true. The segmentation is "leet" (covers 0:4) + "code" (covers 4:8).

The Code

Watch the algorithm try every split point to determine which prefixes can be segmented:

Converting the word list to a set gives O(1) lookups. The break is an optimization - once you find any valid split, dp[i] is true and you can stop checking other j values. Time is O(n^2 * m) in the worst case where m is the average word length (for string slicing and hashing). Space is O(n).

Optimizing with Word Length Bounds

Instead of checking all j from 0 to i-1, you can limit j to values where i - j equals the length of some dictionary word. If the longest word in the dictionary has length L, you only need to check j from max(0, i-L) to i-1. This reduces the inner loop from O(n) to O(L) iterations, which matters when L is much smaller than n.

Practice

The jump game family applies 1D DP to reachability problems. You are given an array where each element represents the maximum jump length from that position. The question is whether you can reach the last index (Jump Game I) or the minimum number of jumps to get there (Jump Game II).

Jump Game I: Can You Reach the End?

Given an array nums where nums[i] is the maximum you can jump forward from index i, determine if you can reach the last index starting from index 0.

DP approach: let dp[i] = true if index i is reachable from index 0. Base case: dp[0] = true. For each index i where dp[i] is true, set dp[i+1] through dp[i + nums[i]] to true (all indices reachable from i). The answer is dp[n-1].

This runs in O(n * max(nums[i])) time, which can be O(n^2) in the worst case. But there is a much simpler O(n) greedy approach.

Greedy approach: maintain a variable max_reach that tracks the farthest index reachable so far. Scan left to right. At each index i, if i > max_reach, you cannot reach this index - return false. Otherwise, update max_reach = max(max_reach, i + nums[i]). If you finish the scan, return true.

The greedy works because reachability is monotonic - if you can reach index i, you can reach all indices between 0 and i (since you passed through them to get to i). So tracking the farthest reachable point is sufficient.

Jump Game II: Minimum Jumps

Now the question is: what is the minimum number of jumps to reach the last index? This requires DP because greedy reachability does not track jump counts.

Let dp[i] = minimum jumps to reach index i. Base case: dp[0] = 0. For each index i, for each jump distance j from 1 to nums[i], update dp[i+j] = min(dp[i+j], dp[i] + 1).

There is also a BFS-like greedy O(n) approach for minimum jumps. Think of each "level" as all indices reachable in the same number of jumps. At each level, compute the farthest you can reach from any index in the current level. That defines the next level. Count levels until you reach or pass the last index.

When DP vs Greedy

Jump Game I is one of the rare cases where greedy is provably optimal and simpler than DP. The key property enabling this is that reachability is monotonic and does not depend on how you reach a position, only whether you reach it.

Jump Game II's greedy works because the BFS-level structure guarantees optimal jump counts. But understanding the DP formulation is still valuable - it generalizes to variants where the greedy property does not hold (e.g., when there are costs associated with landing on certain indices).

Many 1D DP problems use an array of size n, but some can be solved with O(1) space by observing that dp[i] depends only on a fixed number of previous values. This section covers when and how to apply this optimization, and when the full array is genuinely necessary.

The Climbing Stairs Example

The climbing stairs problem asks: how many distinct ways can you climb n stairs if you can take 1 or 2 steps at a time? The recurrence is dp[i] = dp[i-1] + dp[i-2] - the number of ways to reach stair i is the sum of ways to reach the two stairs below it (since you can arrive from either).

With a full array:

Since dp[i] only reads dp[i-1] and dp[i-2], you can replace the entire array with two variables:

This is the same computation but with O(1) space instead of O(n). The variables "slide" forward through the conceptual array, always holding the two values needed for the next step.

When Space Optimization Works

The optimization applies when dp[i] depends only on a bounded window of previous values:

• dp[i] depends on dp[i-1] only (e.g., house robber II without adjacency, simple accumulation): one variable suffices.
• dp[i] depends on dp[i-1] and dp[i-2] (e.g., climbing stairs, Fibonacci, house robber): two variables.
• dp[i] depends on dp[i-1], dp[i-2], and dp[i-3] (e.g., tribonacci): three variables.

The pattern is the same: replace the array with k variables where k is the size of the dependency window, and rotate them at each step.

When Space Optimization Does NOT Work

Not all 1D DP problems can drop the array. The optimization fails when dp[i] depends on arbitrary earlier values, not just a fixed window behind it.

Longest Increasing Subsequence: dp[i] = max(dp[j]+1) for all j < i where nums[j] < nums[i]. Index i might depend on dp[0], dp[3], dp[7] - any subset of previous entries. You cannot predict which entries will be needed, so the full array must be retained.

Word Break: dp[i] depends on dp[j] for any j from 0 to i-1 where s[j:i] is a dictionary word. The relevant split point could be anywhere in the range, so you need the entire dp array up to the current position.

Coin Change: dp[i] = min(dp[i-c]+1) for each coin c. The dependency reaches back by varying distances (the coin values), not a fixed window. With coins [1, 5, 7], dp[11] depends on dp[10], dp[6], and dp[4]. You need the full array.

House Robber as a Space-Optimized DP

The house robber problem asks: given an array of house values, find the maximum sum you can rob without robbing two adjacent houses. The recurrence is dp[i] = max(dp[i-1], dp[i-2] + nums[i]) - either skip house i (take dp[i-1]) or rob house i (take dp[i-2] + nums[i]).

This depends on exactly dp[i-1] and dp[i-2], so two variables work:

For nums = [2, 7, 9, 3, 1]:

• i=1: current = max(2, 0+7) = 7. prev2=2, prev1=7.
• i=2: current = max(7, 2+9) = 11. prev2=7, prev1=11.
• i=3: current = max(11, 7+3) = 11. prev2=11, prev1=11.
• i=4: current = max(11, 11+1) = 12. prev2=11, prev1=12.

Answer: 12 (rob houses with values 2, 9, 1).

Practice