1D dynamic programming

Overview

1D dynamic programming solves problems where the state is a single index or value: dp[i] is the answer for the first i elements, or for a target amount i. Each dp[i] is computed from a few earlier entries by a transition rule, and the final answer is dp[n] or the best over all dp[i].

Most 1D DP problems are variations of a handful of shapes: 'take or skip' (House Robber), 'last step' (Climbing Stairs), 'best ending here' (Kadane, LIS), and 'split the prefix' (Word Break, Decode Ways). Learning to recognize the shape is most of the work.

When to use it

• Input is a single sequence or a single number (amount, n).
• The problem asks for a count of ways, a minimum cost, a maximum value, or feasibility.
• Choices at each index affect only nearby earlier indexes.
• A brute-force recursion f(i) calls f(i - 1), f(i - 2), ... repeatedly.

Problem patterns it solves

Where it is used in real software

Key terms

dp[i]

The answer for the subproblem ending at or containing index i.

Transition

Formula for dp[i] in terms of earlier states.

Base case

dp[0] (and sometimes dp[1]) known directly.

Rolling variables

Keep only the last few dp values to use O(1) space.

Five-step DP method

1. 1
   Define the state

   dp[i] = maximum money robbing houses 0..i (write it as a sentence).

2. 2
   Find the transition

   Either skip house i (dp[i - 1]) or rob it (dp[i - 2] + nums[i]); take the max.

3. 3
   Set base cases

   dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).

4. 4
   Choose the order

   Increasing i, so dependencies are already computed.

5. 5
   Optimize space

   Only dp[i - 1] and dp[i - 2] are read: keep two variables.

Decode Ways for "226"

'1' to '26' map to letters; dp[i] = ways to decode the first i characters

3 decodings: BBF (2, 2, 6), BZ (2, 26), VF (22, 6). A '0' can never stand alone, and two-digit values must be between 10 and 26.

Implementation

1function rob(nums) {2  let prev2 = 0, prev1 = 0; // dp[i - 2], dp[i - 1]3  for (const x of nums) {4    const current = Math.max(prev1, prev2 + x);5    prev2 = prev1;6    prev1 = current;7  }8  return prev1;9}10 11// 213. House Robber II: circle, so exclude either the first or the last house12function robCircle(nums) {13  if (nums.length === 1) return nums[0];14  return Math.max(rob(nums.slice(1)), rob(nums.slice(0, -1)));15}16 17function numDecodings(s) {18  const dp = new Array(s.length + 1).fill(0);19  dp[0] = 1;20  for (let i = 1; i <= s.length; i++) {21    if (s[i - 1] !== "0") dp[i] += dp[i - 1];22    const two = Number(s.slice(i - 2, i));23    if (i >= 2 && two >= 10 && two <= 26) dp[i] += dp[i - 2];24  }25  return dp[s.length];26}27 28function wordBreak(s, wordDict) {29  const words = new Set(wordDict);30  const dp = new Array(s.length + 1).fill(false);31  dp[0] = true;32  for (let i = 1; i <= s.length; i++) {33    for (let j = 0; j < i; j++) {34      if (dp[j] && words.has(s.slice(j, i))) {35        dp[i] = true;36        break;37      }38    }39  }40  return dp[s.length];41}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Off-by-one between dp indexes and input indexes.

  Fix: When dp has n + 1 entries, dp[i] usually refers to the first i elements, so the current element is s[i - 1].

• Wrong base case for counting problems.

  Fix: The empty prefix usually has exactly 1 way.

• Leading zeros in Decode Ways.

  Fix: '0' alone is invalid; '06' is not a valid two-digit code.

Interview questions

Practice problems