DP — 1D Problems (Fibonacci, Climbing Stairs, House Robber)

0/12 in this phase0/57 across the roadmap

📖 Concept

1D DP problems have a single dimension: dp[i] depends on previous values dp[i-1], dp[i-2], etc.

Pattern recognition:

dp[i] = f(dp[i-1]) → linear dependency (can optimize to O(1) space)
dp[i] = f(dp[i-1], dp[i-2]) → two previous values (Fibonacci-like)
dp[i] = f(dp[0...i-1]) → all previous values (LIS pattern)

Top 1D DP problems for interviews:

Fibonacci / Climbing Stairs — dp[i] = dp[i-1] + dp[i-2]
House Robber — dp[i] = max(dp[i-1], dp[i-2] + nums[i])
Coin Change — dp[amount] = min(dp[amount-coin] + 1) for all coins
Longest Increasing Subsequence — dp[i] = max(dp[j] + 1) for j < i where a[j] < a[i]
Word Break — dp[i] = any dp[j] where s[j..i] is in dictionary
Decode Ways — dp[i] = dp[i-1] (valid single) + dp[i-2] (valid double)

Space optimization: If dp[i] only depends on the last k values, you only need k variables instead of an array. This reduces O(n) space to O(1).

🏠 Real-world analogy: 1D DP is like climbing a staircase where each step's cost depends on which previous steps you took. You record the best cost to reach each step, building up to the top.

💻 Code Example

codeTap to expand ⛶

1// COIN CHANGE — Min coins to make amount
2function coinChange(coins: number[], amount: number): number {
3  const dp = new Array(amount + 1).fill(Infinity);
4  dp[0] = 0;
5  for (let i = 1; i <= amount; i++) {
6    for (const coin of coins) {
7      if (coin <= i && dp[i - coin] !== Infinity) {
8        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
9      }
10    }
11  }
12  return dp[amount] === Infinity ? -1 : dp[amount];
13}
14
15// LONGEST INCREASING SUBSEQUENCE — O(n²) DP
16function lengthOfLIS(nums: number[]): number {
17  const dp = new Array(nums.length).fill(1);
18  for (let i = 1; i < nums.length; i++) {
19    for (let j = 0; j < i; j++) {
20      if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
21    }
22  }
23  return Math.max(...dp);
24}
25
26// LIS — O(n log n) with binary search
27function lisOptimal(nums: number[]): number {
28  const tails: number[] = [];
29  for (const num of nums) {
30    let lo = 0, hi = tails.length;
31    while (lo < hi) {
32      const mid = (lo + hi) >>> 1;
33      if (tails[mid] < num) lo = mid + 1;
34      else hi = mid;
35    }
36    tails[lo] = num;
37  }
38  return tails.length;
39}
40
41// WORD BREAK
42function wordBreak(s: string, wordDict: string[]): boolean {
43  const words = new Set(wordDict);
44  const dp = new Array(s.length + 1).fill(false);
45  dp[0] = true;
46  for (let i = 1; i <= s.length; i++) {
47    for (let j = 0; j < i; j++) {
48      if (dp[j] && words.has(s.substring(j, i))) {
49        dp[i] = true;
50        break;
51      }
52    }
53  }
54  return dp[s.length];
55}
56
57// DECODE WAYS — "226" → "BZ"(2,26) or "VF"(22,6) or "BBF"(2,2,6)
58function numDecodings(s: string): number {
59  if (s[0] === '0') return 0;
60  let prev2 = 1, prev1 = 1;
61  for (let i = 1; i < s.length; i++) {
62    let curr = 0;
63    if (s[i] !== '0') curr += prev1;
64    const twoDigit = parseInt(s.substring(i-1, i+1));
65    if (twoDigit >= 10 && twoDigit <= 26) curr += prev2;
66    prev2 = prev1;
67    prev1 = curr;
68  }
69  return prev1;
70}
71
72// MAXIMUM PRODUCT SUBARRAY
73function maxProduct(nums: number[]): number {
74  let maxProd = nums[0], minProd = nums[0], result = nums[0];
75  for (let i = 1; i < nums.length; i++) {
76    if (nums[i] < 0) [maxProd, minProd] = [minProd, maxProd];
77    maxProd = Math.max(nums[i], maxProd * nums[i]);
78    minProd = Math.min(nums[i], minProd * nums[i]);
79    result = Math.max(result, maxProd);
80  }
81  return result;
82}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

Coin change — minimum coins to make amount
Coin change II — count ways to make amount
Longest increasing subsequence
Word break — can string be segmented?
Decode ways — count valid decodings
Maximum product subarray
Perfect squares — min number of squares that sum to n
Palindrome partitioning II — min cuts for palindrome substrings
Jump game — can you reach the end? (also solvable with greedy)
Delete and earn — maximize points from operations

⚠️ Common Mistakes

Not handling zero in decode ways — '0' is invalid alone, but '10' and '20' are valid
Forgetting that LIS has both O(n²) and O(n log n) solutions — interviewers often expect the faster one
Not tracking both max and min product in max product subarray — negative × negative = positive
Initializing dp array with wrong values — often should be 0, Infinity, or -Infinity depending on min/max
Not considering the coin change 'impossible' case — return -1 if amount can't be made

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for DP — 1D Problems (Fibonacci, Climbing Stairs, House Robber)

Was this topic helpful?

← PreviousDynamic Programming — Introduction & Thinking Next →DP — 2D Problems (Grid, LCS, Edit Distance)