1-D Dynamic Programming

Many DP problems need only a single array indexed by one variable. Once the recurrence is identified, filling the array is mechanical — and when dp[i] depends only on the previous one or two values, the entire array collapses to a pair of variables.

Climbing Stairs

Problem: An n-step staircase; each step you climb 1 or 2 steps. How many distinct ways reach the top?

State: dp[i] = number of ways to reach step i. Recurrence: dp[i] = dp[i-1] + dp[i-2] Base cases: dp[0] = 1, dp[1] = 1

function climbStairs(n) {
  let prev2 = 1, prev1 = 1;
  for (let i = 2; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

console.log(climbStairs(10)); // 89

Time O(n), space O(1) — the Fibonacci recurrence with different base cases.

House Robber

Problem: An array of house values; you cannot rob two adjacent houses. Maximize total value stolen.

State: dp[i] = max value robbing from houses 0..i. Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) Base cases: dp[0] = nums[0], dp[1] = max(nums[0], nums[1])

function rob(nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];
  let prev2 = nums[0];
  let prev1 = Math.max(nums[0], nums[1]);
  for (let i = 2; i < nums.length; i++) {
    const curr = Math.max(prev1, prev2 + nums[i]);
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

console.log(rob([2, 7, 9, 3, 1])); // 12  (rob houses 0, 2, 4)

Decode Ways

Problem: A string of digits encodes letters where ‘A’=1 … ‘Z’=26. Count distinct decodings.

State: dp[i] = number of ways to decode the first i characters. Recurrence:

• If s[i-1] is not ‘0’: dp[i] += dp[i-1]
• If the two-digit number formed by s[i-2]s[i-1] is between 10 and 26: dp[i] += dp[i-2] Base cases: dp[0] = 1 (empty string), dp[1] = s[0] !== '0' ? 1 : 0

function numDecodings(s) {
  const n = s.length;
  let prev2 = 1;
  let prev1 = s[0] !== '0' ? 1 : 0;
  for (let i = 2; i <= n; i++) {
    let curr = 0;
    const oneDigit = Number(s[i - 1]);
    const twoDigit = Number(s.slice(i - 2, i));
    if (oneDigit >= 1) curr += prev1;
    if (twoDigit >= 10 && twoDigit <= 26) curr += prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

console.log(numDecodings('226')); // 3 — (2,2,6), (22,6), (2,26)

Pattern Summary

When the recurrence only looks back a fixed number of positions, you can always trade the full dp array for that many scalar variables.

Up Next

Move to two-dimensional DP where the state tracks both a row and a column position, and see how row-rolling keeps space linear.