templates · Dynamic programming

1D DP

  • "How many ways", "minimum cost" or "maximum total" along a line of items
  • The answer at position i depends only on a few earlier positions (i - 1, i - 2)
  • A plain recursion works but repeats the same calls again and again

1D DP

the one rule

The invariant

When the loop reaches i, every dp[j] with j < i is already final and correct.

write it from memory

The template

dp array

javajava.util.*
/** House Robber: best total from houses 0..n-1 when you may not take two neighbours. */static int bestTable(int[] nums) {    int n = nums.length;    if (n == 0) return 0;                                // nothing to take    int[] dp = new int[n];                               // dp[i] = best total using houses 0..i    dp[0] = nums[0];                                     // base case: one house    for (int i = 1; i < n; i++) {        int skip = dp[i - 1];                            // leave house i        int take = nums[i] + (i >= 2 ? dp[i - 2] : 0);   // take house i, so skip i-1        dp[i] = Math.max(skip, take);                    // the choice at i    }    return dp[n - 1];}

Write the meaning of dp[i] in one sentence first. Base case, transition and answer all follow from that sentence.

fill in the blanks — only these lines change per problem

  1. line 5What dp[i] means for this problem: ways to reach step i, best total up to i, ways to decode the first i letters.
  2. line 6The smallest cases you can answer without the recurrence, e.g. dp[0] = 1 for counting ways.
  3. line 10How dp[i] is built from earlier values: + for counting, max/min for best.
  4. line 12Which cell is the answer: usually dp[n - 1] or dp[n], sometimes the max over all dp[i].

two rolling variables

javajava.util.*
/** Same answer, but dp[i] only needs dp[i-1] and dp[i-2]: keep two variables. */static int bestRolling(int[] nums) {    int prev2 = 0;                                       // dp[i-2]    int prev1 = 0;                                       // dp[i-1]    for (int x : nums) {        int cur = Math.max(prev1, x + prev2);        prev2 = prev1;                                   // slide the window forward        prev1 = cur;    }    return prev1;}

Same recurrence, O(1) space. Write the table version first in an interview, then roll it if asked.

fill in the blanks — only these lines change per problem

  1. line 7Move the two variables one step forward, in the right order, so nothing is overwritten too early.

complexity

What it costs

time O(n)
One pass over the items, and each dp[i] is O(1) work from the earlier values.
space O(n), or O(1) rolling
The table keeps one value per index. The rolling version keeps only the two values the transition reads.

watch out

Common bugs

  • Off-by-one in the size: if dp[i] means "the first i items", the array needs n + 1 cells.
  • Forgetting the empty or one-item input before reading dp[0] or dp[1].
  • In the rolling version, updating prev1 before saving it into prev2.

use it

Practise it on

learn it properly