1D DP Patterns - Data Structures & Algorithms

1D DP problems are the most common type we’ll see in interviews. The pattern is simple: dp[i] depends on some previous values like dp[i-1], dp[i-2], etc. We fill a single array from left to right.

Once we nail these, the harder DP problems are just extensions of the same idea.

Climbing Stairs

Problem: We can climb 1 or 2 steps at a time. How many distinct ways to reach step n?

This is literally Fibonacci in disguise. To reach step i, we either came from step i-1 (took 1 step) or step i-2 (took 2 steps).

State: dp[i] = number of ways to reach step i

Recurrence: dp[i] = dp[i-1] + dp[i-2]

function climbStairs(n) {
  if (n <= 2) return n;
  let prev2 = 1, prev1 = 2;      // dp[1] = 1, dp[2] = 2
  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2;   // two ways to arrive here
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}
// Time: O(n), Space: O(1)

def climb_stairs(n):
    if n <= 2:
        return n
    prev2, prev1 = 1, 2           # dp[1] = 1, dp[2] = 2
    for i in range(3, n + 1):
        curr = prev1 + prev2      # two ways to arrive here
        prev2 = prev1
        prev1 = curr
    return prev1
# Time: O(n), Space: O(1)

static int climbStairs(int n) {
    if (n <= 2) return n;
    int prev2 = 1, prev1 = 2;      // dp[1] = 1, dp[2] = 2
    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2;   // two ways to arrive here
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}
// Time: O(n), Space: O(1)

House Robber

Problem: We’re a robber with a row of houses. Each has some money. We can’t rob two adjacent houses (alarm triggers). Find the max money we can steal.

At each house we have a choice: rob it (take its money + best from 2 houses back) or skip it (keep the best from the previous house).

State: dp[i] = max money we can get from the first i houses

Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i])

House Robber Decision — nums = [2, 7, 9, 3, 1]

rob

skip

rob

skip

rob

Best: $2 + $9 + $1 = $12

function rob(nums) {
  if (nums.length === 1) return nums[0];
  let prev2 = 0, prev1 = 0;
  for (const money of nums) {
    const curr = Math.max(prev1, prev2 + money); // skip or rob
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}
// Time: O(n), Space: O(1)

def rob(nums):
    if len(nums) == 1:
        return nums[0]
    prev2, prev1 = 0, 0
    for money in nums:
        curr = max(prev1, prev2 + money)  # skip or rob
        prev2 = prev1
        prev1 = curr
    return prev1
# Time: O(n), Space: O(1)

static int rob(int[] nums) {
    if (nums.length == 1) return nums[0];
    int prev2 = 0, prev1 = 0;
    for (int money : nums) {
        int curr = Math.max(prev1, prev2 + money); // skip or rob
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}
// Time: O(n), Space: O(1)

Coin Change

Problem: Given coin denominations and a target amount, find the minimum number of coins needed. If it’s impossible, return -1.

This one is different from the above — instead of looking at just i-1 and i-2, we look at dp[i - coin] for every coin denomination.

State: dp[i] = minimum coins to make amount i

Recurrence: dp[i] = min(dp[i - coin] + 1) for each coin

Let’s see both memoized and tabulated approaches.

Memoized (Top-Down)

function coinChange(coins, amount) {
  const memo = {};
  function dp(rem) {
    if (rem === 0) return 0;           // no coins needed
    if (rem < 0) return Infinity;       // invalid path
    if (rem in memo) return memo[rem];
    let best = Infinity;
    for (const coin of coins) {
      best = Math.min(best, dp(rem - coin) + 1);
    }
    return memo[rem] = best;
  }
  const res = dp(amount);
  return res === Infinity ? -1 : res;
}

def coin_change(coins, amount):
    memo = {}
    def dp(rem):
        if rem == 0: return 0           # no coins needed
        if rem < 0: return float('inf') # invalid path
        if rem in memo: return memo[rem]
        best = float('inf')
        for coin in coins:
            best = min(best, dp(rem - coin) + 1)
        memo[rem] = best
        return best
    res = dp(amount)
    return -1 if res == float('inf') else res

static int coinChange(int[] coins, int amount) {
    Map<Integer, Integer> memo = new HashMap<>();
    int res = dp(coins, amount, memo);
    return res == Integer.MAX_VALUE ? -1 : res;
}
static int dp(int[] coins, int rem, Map<Integer, Integer> memo) {
    if (rem == 0) return 0;
    if (rem < 0) return Integer.MAX_VALUE;
    if (memo.containsKey(rem)) return memo.get(rem);
    int best = Integer.MAX_VALUE;
    for (int coin : coins) {
        int sub = dp(coins, rem - coin, memo);
        if (sub != Integer.MAX_VALUE) best = Math.min(best, sub + 1);
    }
    memo.put(rem, best);
    return best;
}

Tabulated (Bottom-Up)

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;                          // base case: 0 coins for $0
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (i - coin >= 0) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}
// Time: O(amount * coins), Space: O(amount)

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0                          # base case: 0 coins for $0
    for i in range(1, amount + 1):
        for coin in coins:
            if i - coin >= 0:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return -1 if dp[amount] == float('inf') else dp[amount]
# Time: O(amount * coins), Space: O(amount)

static int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;                          // base case: 0 coins for $0
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i - coin >= 0 && dp[i - coin] != Integer.MAX_VALUE) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
// Time: O(amount * coins), Space: O(amount)

Longest Increasing Subsequence (LIS)

Problem: Find the length of the longest strictly increasing subsequence.

For each element, we check all previous elements — if they’re smaller, we can extend their subsequence.

State: dp[i] = length of LIS ending at index i

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

function lengthOfLIS(nums) {
  const dp = new Array(nums.length).fill(1); // each element is a subsequence of length 1
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1); // extend the subsequence
      }
    }
  }
  return Math.max(...dp);
}
// Time: O(n²), Space: O(n)

def length_of_lis(nums):
    dp = [1] * len(nums)  # each element is a subsequence of length 1
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)  # extend the subsequence
    return max(dp)
# Time: O(n²), Space: O(n)

static int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);  // each element is a subsequence of length 1
    int maxLen = 1;
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
}
// Time: O(n²), Space: O(n)

There’s an O(n log n) solution using binary search + patience sorting, but the O(n²) DP approach is what interviewers want us to explain first.

Word Break

Problem: Given a string and a dictionary of words, can we segment the string into a space-separated sequence of dictionary words?

State: dp[i] = true if the substring s[0..i-1] can be segmented

Recurrence: dp[i] = true if there’s some j < i where dp[j] is true AND s[j..i] is in the dictionary

function wordBreak(s, wordDict) {
  const words = new Set(wordDict);
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;                        // empty string is valid
  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && words.has(s.slice(j, i))) {
        dp[i] = true;
        break;                          // found one valid split
      }
    }
  }
  return dp[s.length];
}

def word_break(s, word_dict):
    words = set(word_dict)
    dp = [False] * (len(s) + 1)
    dp[0] = True                        # empty string is valid
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break                   # found one valid split
    return dp[len(s)]

static boolean wordBreak(String s, List<String> wordDict) {
    Set<String> words = new HashSet<>(wordDict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;                       // empty string is valid
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && words.contains(s.substring(j, i))) {
                dp[i] = true;
                break;                  // found one valid split
            }
        }
    }
    return dp[s.length()];
}

The 1D DP Pattern Cheat Sheet

Here’s the mental model for all 1D DP problems:

Define dp[i] — what does the answer at position i mean?
Find the transition — which previous states does dp[i] depend on?
Set base cases — dp[0], dp[1], etc.
Loop and fill — iterate through the array, filling each dp[i]
Return the answer — usually dp[n] or max(dp)

If dp[i] only depends on the last 1-2 values, we can optimize space to O(1). If it depends on all previous values (like LIS), we need O(n) space.