1D Dynamic Programming
What Is 1D DP?
A DP problem is 1D when the state can be captured by a single index. The dp table is a 1D array where dp[i] represents the answer for a sub-problem defined by position i.
1D DP PATTERN: dp[i] = answer for the sub-problem at/up to position i dp[i] = f(dp[i-1], dp[i-2], ..., dp[i-k], input[i]) Single index captures all necessary state. Table is a 1D array of length n (or n+1). COMMON 1D DP SHAPES: "Best up to i": dp[i] = best answer using elements 0..i "Reachable at i": dp[i] = can we reach position i? "Ways to reach i": dp[i] = number of ways to reach i "Ending at i": dp[i] = best answer for sub-sequence ENDING at i "Segmentable to i": dp[i] = can s[0..i-1] be broken into valid words? 1D VS 2D SIGNAL: 1D: single constraint (position, amount, or index) 2D: two constraints (two strings, item+capacity, two pointers)
Pattern 1: Linear Sequence DP
Problems where the answer at position i depends on a fixed number of previous positions.
House Robber
PROBLEM: Rob houses, can't rob adjacent. Maximise total.
STATE: dp[i] = max money robbing houses 0..i
RECUR: dp[i] = max(dp[i-1], ← skip house i
dp[i-2] + nums[i]) ← rob house i (skip i-1)
BASE: dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
ANSWER: dp[n-1]
Trace for nums = [2, 7, 9, 3, 1]:
dp[0] = 2
dp[1] = max(2,7) = 7
dp[2] = max(7, 2+9) = 11
dp[3] = max(11, 7+3) = 11
dp[4] = max(11, 11+1) = 12 ← rob houses 0+2+4 = 2+9+1
Min Cost Climbing Stairs
PROBLEM: Each stair costs cost[i] to leave. Min total to reach top.
STATE: dp[i] = min cost to REACH step i (before paying to leave)
RECUR: dp[i] = min(dp[i-1] + cost[i-1], ← arrived from step i-1
dp[i-2] + cost[i-2]) ← arrived from step i-2
BASE: dp[0] = 0, dp[1] = 0 (can start at either step free)
ANSWER: dp[n] (one past last stair = top)
Trace for cost = [10, 15, 20]:
n=3 (top = index 3)
dp[0]=0, dp[1]=0
dp[2] = min(0+15, 0+10) = 10
dp[3] = min(10+20, 0+15) = 15 ← start at step 1, pay 15
Pattern 2: Jump Game
Problems where you choose a jump size at each position.
Jump Game I — Can You Reach the End?
PROBLEM: Given nums[i] = max jump from i. Can you reach last index?
DP APPROACH — O(n²):
dp[i] = can we reach index i?
dp[0] = true (start here)
dp[i] = any j < i where dp[j]=true AND nums[j] >= i-j
GREEDY APPROACH — O(n) (better):
maxReach = 0
for i in 0..n-1:
if i > maxReach: return false ← can't reach i
maxReach = max(maxReach, i + nums[i])
return true
Trace for nums = [2,3,1,1,4]:
i=0: maxReach=max(0,0+2)=2
i=1: maxReach=max(2,1+3)=4
i=2: maxReach=max(4,2+1)=4
i=3: maxReach=max(4,3+1)=4
i=4: maxReach=max(4,4+4)=8
Reached end ✓
Trace for nums = [3,2,1,0,4]:
i=0: maxReach=3
i=1: maxReach=3
i=2: maxReach=3
i=3: maxReach=3
i=4: 4 > maxReach=3 → CANNOT REACH ✗
Jump Game II — Minimum Jumps to Reach End
PROBLEM: Minimum number of jumps to reach last index.
DP APPROACH — O(n²):
dp[i] = min jumps to reach index i
dp[0] = 0
dp[i] = min(dp[j] + 1) for all j < i where j + nums[j] >= i
GREEDY APPROACH — O(n):
jumps = 0, curEnd = 0, farthest = 0
for i in 0..n-2:
farthest = max(farthest, i + nums[i])
if i == curEnd:
jumps++
curEnd = farthest
return jumps
Trace for nums = [2,3,1,1,4]:
i=0: farthest=2, i==curEnd(0) → jump=1, curEnd=2
i=1: farthest=max(2,1+3)=4
i=2: farthest=max(4,2+1)=4, i==curEnd(2) → jump=2, curEnd=4
i=3: farthest=max(4,3+1)=4
Done: 2 jumps ✓
Pattern 3: Counting Ways
Problems asking how many ways to reach a state.
Climbing Stairs
STATE: dp[i] = ways to reach step i
RECUR: dp[i] = dp[i-1] + dp[i-2]
(from step i-1 via 1-step, or from step i-2 via 2-step)
BASE: dp[0] = 1, dp[1] = 1
ANSWER: dp[n]
Same as Fibonacci shifted: ways(n) = fib(n+1)
Decode Ways
PROBLEM: '1'-'26'→A-Z. Count decodings of string s.
STATE: dp[i] = number of ways to decode s[0..i-1]
RECUR: dp[i] = (dp[i-1] if s[i-1] != '0') ← single digit
+ (dp[i-2] if 10 <= two_digit <= 26) ← two digits
BASE: dp[0] = 1 (empty string: 1 way)
dp[1] = 1 if s[0]!='0' else 0
Trace for s = "226":
dp[0]=1, dp[1]=1 (s[0]='2'≠0)
dp[2]: s[1]='2'≠0 → +dp[1]=1; two_digit="22"=22 in [10,26] → +dp[0]=1; dp[2]=2
dp[3]: s[2]='6'≠0 → +dp[2]=2; two_digit="26"=26 in [10,26] → +dp[1]=1; dp[3]=3
Decodings of "226": BBF, BZ, VF → 3 ways ✓
Trace for s = "06":
dp[0]=1
dp[1]: s[0]='0' → single invalid → dp[1]=0
dp[2]: s[1]='6'≠0 → +dp[1]=0; two_digit="06"=6 NOT in [10,26] → dp[2]=0
0 decodings (leading zero) ✓
Pattern 4: Reachability / Feasibility
Problems asking if a particular state is achievable.
Word Break
PROBLEM: Can string s be segmented into dictionary words?
STATE: dp[i] = can s[0..i-1] be segmented?
RECUR: dp[i] = any j in [0,i) where dp[j]=true
AND s[j..i-1] in wordDict
BASE: dp[0] = true (empty string: trivially segmentable)
ANSWER: dp[len(s)]
Trace for s="leetcode", dict={"leet","code","lee","t"}:
dp[0]=T
dp[1]: j=0: dp[0]=T, "l"∉dict. dp[1]=F
dp[2]: j=0: "le"∉dict; j=1: dp[1]=F. dp[2]=F
dp[3]: j=0: "lee"∈dict! dp[3]=T
dp[4]: j=0: "leet"∈dict! dp[4]=T
dp[5]: j=3: dp[3]=T,"co"∉dict; j=4: dp[4]=T,"c"∉dict. dp[5]=F
dp[6]: j=4: dp[4]=T,"co"∉dict. dp[6]=F
dp[7]: j=4: dp[4]=T,"cod"∉dict. dp[7]=F
dp[8]: j=4: dp[4]=T,"code"∈dict! dp[8]=T
Answer: dp[8]=true → "leet"+"code" ✓
Complete Implementations
1import java.util.*;
2
3public class OneDimDP {
4
5 // ── House Robber ─────────────────────────────────────────────────
6 public static int rob(int[] nums) {
7 int n = nums.length;
8 if (n == 1) return nums[0];
9 int[] dp = new int[n];
10 dp[0] = nums[0];
11 dp[1] = Math.max(nums[0], nums[1]);
12 for (int i = 2; i < n; i++) {
13 dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
14 }
15 return dp[n-1];
16 }
17
18 // O(1) space — rolling two variables
19 public static int robOpt(int[] nums) {
20 int prev2 = 0, prev1 = 0;
21 for (int num : nums) {
22 int curr = Math.max(prev1, prev2 + num);
23 prev2 = prev1;
24 prev1 = curr;
25 }
26 return prev1;
27 }
28
29 // ── Min Cost Climbing Stairs ──────────────────────────────────────
30 public static int minCostClimbingStairs(int[] cost) {
31 int n = cost.length;
32 int[] dp = new int[n + 1];
33 dp[0] = 0; dp[1] = 0;
34 for (int i = 2; i <= n; i++) {
35 dp[i] = Math.min(dp[i-1] + cost[i-1],
36 dp[i-2] + cost[i-2]);
37 }
38 return dp[n];
39 }
40
41 // ── Jump Game I — Can reach end? ──────────────────────────────────
42 public static boolean canJump(int[] nums) {
43 int maxReach = 0;
44 for (int i = 0; i < nums.length; i++) {
45 if (i > maxReach) return false; // Gap: can't reach i
46 maxReach = Math.max(maxReach, i + nums[i]);
47 }
48 return true;
49 }
50
51 // ── Jump Game II — Min jumps ──────────────────────────────────────
52 public static int jump(int[] nums) {
53 int jumps = 0, curEnd = 0, farthest = 0;
54 for (int i = 0; i < nums.length - 1; i++) {
55 farthest = Math.max(farthest, i + nums[i]);
56 if (i == curEnd) { // Exhausted current jump range
57 jumps++;
58 curEnd = farthest;
59 }
60 }
61 return jumps;
62 }
63
64 // ── Decode Ways ──────────────────────────────────────────────────
65 public static int numDecodings(String s) {
66 int n = s.length();
67 if (s.charAt(0) == '0') return 0;
68
69 int[] dp = new int[n + 1];
70 dp[0] = 1; // Empty string: 1 way
71 dp[1] = 1; // Single non-zero digit: 1 way
72
73 for (int i = 2; i <= n; i++) {
74 // Single digit: s[i-1] != '0'
75 if (s.charAt(i-1) != '0') {
76 dp[i] += dp[i-1];
77 }
78
79 // Two digits: 10 <= two_digit <= 26
80 int twoDigit = Integer.parseInt(s.substring(i-2, i));
81 if (twoDigit >= 10 && twoDigit <= 26) {
82 dp[i] += dp[i-2];
83 }
84 }
85
86 return dp[n];
87 }
88
89 // ── Word Break ───────────────────────────────────────────────────
90 public static boolean wordBreak(String s, List<String> wordDict) {
91 Set<String> dict = new HashSet<>(wordDict);
92 int n = s.length();
93 boolean[] dp = new boolean[n + 1];
94 dp[0] = true; // Empty string: can always be segmented
95
96 for (int i = 1; i <= n; i++) {
97 for (int j = 0; j < i; j++) {
98 if (dp[j] && dict.contains(s.substring(j, i))) {
99 dp[i] = true;
100 break;
101 }
102 }
103 }
104
105 return dp[n];
106 }
107
108 // ── Climbing Stairs ──────────────────────────────────────────────
109 public static int climbStairs(int n) {
110 if (n <= 2) return n;
111 int prev2 = 1, prev1 = 2;
112 for (int i = 3; i <= n; i++) {
113 int curr = prev1 + prev2;
114 prev2 = prev1; prev1 = curr;
115 }
116 return prev1;
117 }
118
119 public static void main(String[] args) {
120 System.out.println("Rob [2,7,9,3,1]: " + rob(new int[]{2,7,9,3,1})); // 12
121 System.out.println("RobOpt [2,7,9,3,1]:" + robOpt(new int[]{2,7,9,3,1})); // 12
122 System.out.println("MinCost [10,15,20]: " + minCostClimbingStairs(new int[]{10,15,20})); // 15
123 System.out.println("CanJump [2,3,1,1,4]:" + canJump(new int[]{2,3,1,1,4})); // true
124 System.out.println("CanJump [3,2,1,0,4]:" + canJump(new int[]{3,2,1,0,4})); // false
125 System.out.println("Jump II [2,3,1,1,4]:" + jump(new int[]{2,3,1,1,4})); // 2
126 System.out.println("Decode '226': " + numDecodings("226")); // 3
127 System.out.println("Decode '06': " + numDecodings("06")); // 0
128 System.out.println("WordBreak 'leetcode':" + wordBreak("leetcode",
129 Arrays.asList("leet","code"))); // true
130 System.out.println("ClimbStairs(5): " + climbStairs(5)); // 8
131 }
132}Output:
Rob [2,7,9,3,1]: 12
MinCost [10,15,20]: 15
CanJump [2,3,1,1,4]: true
CanJump [3,2,1,0,4]: false
JumpII [2,3,1,1,4]: 2
Decode '226': 3
Decode '06': 0
WordBreak leetcode: true
ClimbStairs(5): 8
Pattern Recognition Guide
PROBLEM SAYS... LIKELY 1D DP PATTERN ──────────────────────────────────────────────────────────────── "maximise / minimise" Optimisation — dp[i] = max/min "how many ways" Counting — dp[i] = dp[i-1]+dp[i-2] "can you reach" Feasibility — dp[i] = bool "can it be segmented" Reachability — dp[i] = bool from j "jump from position" Jump pattern — track max reach "cannot use adjacent" Two-back dependency — dp[i-2]+val "minimum cost to reach" Cost propagation — dp[i-1]+cost "decode / interpret" Conditional adding dp[i-1]+dp[i-2] DECIDE STATE MEANING: "using elements 0..i" → dp[i] = best considering first i+1 "at position i" → dp[i] = answer exactly at index i "ending at i" → dp[i] = answer for sub-problem ending here "reachable from 0..i-1" → dp[i] = can we get here? DECIDE OPERATION: "how many paths/ways" → sum (dp[i-1] + dp[i-2] + ...) "best value/cost" → max or min over choices "is it possible" → OR over choices (dp[j] AND condition)
Space Optimisation Summary
WHEN: dp[i] depends only on the last k values.
HOW: Replace array with k rolling variables.
k=1 (depends on dp[i-1] only):
prev = dp[0]
for i in 1..n:
curr = f(prev, input[i])
prev = curr
return prev
k=2 (depends on dp[i-1] and dp[i-2]):
prev2, prev1 = dp[0], dp[1]
for i in 2..n:
curr = f(prev1, prev2, input[i])
prev2 = prev1
prev1 = curr
return prev1
APPLIES TO: Fibonacci, Climbing Stairs, House Robber, Min Cost Stairs
DOES NOT APPLY: Word Break (needs dp[j] for any j < i, not just last 2)
Complexity Summary
| Problem | Time | Space | Space Optimised |
|---|---|---|---|
| House Robber | O(n) | O(n) | O(1) |
| Min Cost Climbing Stairs | O(n) | O(n) | O(1) |
| Jump Game I | O(n) | O(1) | Already O(1) (greedy) |
| Jump Game II | O(n) | O(1) | Already O(1) (greedy) |
| Decode Ways | O(n) | O(n) | O(1) (only dp[i-1], dp[i-2]) |
| Word Break | O(n²) | O(n) | Cannot reduce (needs all dp[j]) |
| Climbing Stairs | O(n) | O(n) | O(1) |
Common Mistakes
House Robber: initialising dp[1] as nums[1] instead of max(nums[0], nums[1]). dp[1] = "best money using houses 0..1" which is the richer of the two, not just nums[1]. This initialisation error causes wrong answers when nums[0] > nums[1].
Decode Ways: checking two-digit range as 01-26 instead of 10-26. Single-digit '0' is invalid — "06" cannot decode as '0'+'6'. The two-digit range is [10,26]. If the first digit is '0' (like "06"), the two-character string "06" = 6 which is outside [10,26], so the two-digit decode is correctly rejected.
Word Break: forgetting dp[0] = true. dp[0] = true represents the empty prefix being trivially segmentable. Without it, dp[j] is always false for all j < length of first word, making the entire dp array false. The empty string base case is the anchor.
Jump Game: using DP when greedy is simpler and faster. The DP approach for Jump Game I is O(n²). The greedy max-reach approach is O(n). For interviews, knowing the greedy solution is often expected. However the DP approach builds intuition for Jump Game II.
Rolling variable update order. For House Robber O(1) space: compute curr = max(prev1, prev2 + nums[i]) BEFORE updating prev1 and prev2. If you update prev1 = curr first then prev2 = prev1, you've set prev2 to the NEW prev1 value — wrong. Always compute the new value first, then shift the old values backward.
Interview Questions
Q: House Robber has two variations — circular (first and last house are adjacent) and tree. How do they change the approach?
Circular: the circle constraint means house 0 and house n-1 can't both be robbed. Split into two sub-problems: rob houses 0..n-2 (skip last) and rob houses 1..n-1 (skip first). Return the maximum of both. Both sub-problems are standard linear House Robber — O(n) each. Tree: use DFS post-order. Each node returns a pair (rob_this_node, skip_this_node). rob = node.val + sum of skip values for children. skip = sum of max(rob, skip) for each child. O(n) time.
Q: Word Break is O(n²). Can it be done faster?
With a Trie of the dictionary, checking if s[j..i] is a valid word takes O(i-j) instead of O(i-j) for hash set (same asymptotically). The bottleneck is the O(n²) split points — can't avoid checking all splits in the worst case. However, with the optimisation of only checking splits at positions where dp[j]=true, average case is much better. For competitive programming, suffix automata or Aho-Corasick can reduce to O(n) in some formulations, but the standard O(n²) is acceptable for interview.
Q: How do you recognise that Jump Game has a greedy solution rather than requiring DP?
The greedy insight: at each position, the only information you need is the farthest index reachable so far. You never need to know exactly which positions are reachable — just the maximum reach. If the farthest reach at position i is ≥ n-1, you can reach the end. This is a monotone property: if you can reach position x, you can also "reach" positions 0..x (just stop early). When the optimal sub-structure simplifies to tracking a single maximal value forward, greedy usually replaces DP.
Summary
1D DP problems encode the full state in a single index. The dp table is a 1D array where dp[i] answers the sub-problem for position/count/amount i.
Four main 1D patterns:
| Pattern | Operation | Representative problems |
|---|---|---|
| Linear sequence | max/min of skip vs take | House Robber, Min Cost Stairs |
| Jump / reach | max of reachable range | Jump Game I/II |
| Counting ways | sum of ways to arrive | Climbing Stairs, Decode Ways |
| Feasibility | OR over valid splits | Word Break |
Key transitions:
- ›
dp[i] = max(dp[i-1], dp[i-2] + nums[i])— two-back choice (House Robber) - ›
dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])— cost propagation - ›
dp[i] = dp[i-1] + dp[i-2]— counting (Climbing Stairs, Decode Ways partial) - ›
dp[i] = any j: dp[j] AND condition(j,i)— split-point feasibility (Word Break)
Space optimisation: whenever dp[i] depends only on the last k values, replace the array with k rolling variables — O(n) → O(1) for House Robber, Fibonacci, Climbing Stairs, Decode Ways.
In the next topic you will explore 2D Dynamic Programming — problems requiring two indices to capture the full state, including grid paths, string comparison, and interval problems.
House Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). What does dp[i-1] represent as a CHOICE, not just a value?