1D Dynamic Programming

A café offers you shifts on five days in a row. Each day pays a different amount: 5, 9, 6, 1, 4. There is one rule: after a shift you need a day off, so you can never work two days in a row. Which days should you take to earn the most?

Grabbing the best-paid day first gets you the 9, which rules out the 5 and the 6. Add the 4 at the end and you have 13. But 5 + 6 + 4 = 15. Once again a choice that looked good locally blocked better choices next to it. You need to weigh every day against its neighbours, and a one-row table does exactly that.

#The five steps

Use the recipe from Introduction to Dynamic Programming. The question to settle first is what one cell means.

1. State. best[i] is the most you can earn using only days 0 to i. Ignore the future; just answer for this stretch of days.
2. Recurrence. On day i you either rest or work. If you rest, day i adds nothing and you keep best[i − 1]. If you work, you earn pay[i], but day i − 1 must be free, so you add best[i − 2]. Take the larger: best[i] = max(best[i − 1], pay[i] + best[i − 2]).
3. Base cases. best[0] = pay[0], and best[1] = max(pay[0], pay[1]), because you can take only one of the first two days.
4. Order. Each cell reads the two cells to its left, so fill left to right.
5. Answer. best[n − 1], the best over all the days.

The recurrence works because the two options cover every possible plan. Any plan either uses day i or it does not. If it does not, it is just a plan for the earlier days, and the best of those is best[i − 1]. If it does, the rest of it is a plan for days 0 to i − 2, and the best of those is best[i − 2].

#Fill the table by hand

best[0] = pay[0]best[1] = max(pay[0], pay[1])for i from 2 to n - 1:  rest = best[i - 1]  work = pay[i] + best[i - 2]  best[i] = max(rest, work)return best[n - 1]

The table gives the best total, not the days. To find the days, walk back from the last cell. If a cell equals the one to its left, that day was a rest day: step one cell left. If it is bigger, that day was worked: write it down and jump two cells left. best[4] = 15 is bigger than best[3] = 11, so day 4 is worked and you jump to best[2]. 11 is bigger than best[1] = 9, so day 2 is worked and you jump to best[0], which is day 0. Days 0, 2 and 4.

#The code, then less memory

function maxPay(pay) {
  const n = pay.length;
  if (n === 0) return 0;
  if (n === 1) return pay[0];
  const best = new Array(n);
  best[0] = pay[0];
  best[1] = Math.max(pay[0], pay[1]);
  for (let i = 2; i < n; i++) {
    const rest = best[i - 1];
    const work = pay[i] + best[i - 2];
    best[i] = Math.max(rest, work);
  }
  return best[n - 1];
}
 
maxPay([5, 9, 6, 1, 4]); // 15

def max_pay(pay):
    n = len(pay)
    if n == 0:
        return 0
    if n == 1:
        return pay[0]
    best = [0] * n
    best[0] = pay[0]
    best[1] = max(pay[0], pay[1])
    for i in range(2, n):
        rest = best[i - 1]
        work = pay[i] + best[i - 2]
        best[i] = max(rest, work)
    return best[n - 1]
 
max_pay([5, 9, 6, 1, 4])  # 15

Look at what each step reads: only the two most recent cells. Everything further left is never touched again. So you can keep two variables instead of a whole array. Starting both at 0 also removes the special cases, because "the best before any days" is 0.

function maxPayLowMemory(pay) {
  let twoBack = 0; // best up to day i - 2
  let oneBack = 0; // best up to day i - 1
  for (const p of pay) {
    const current = Math.max(oneBack, p + twoBack);
    twoBack = oneBack; // slide the window right by one day
    oneBack = current;
  }
  return oneBack;
}

def max_pay_low_memory(pay):
    two_back = 0  # best up to day i - 2
    one_back = 0  # best up to day i - 1
    for p in pay:
        current = max(one_back, p + two_back)
        two_back = one_back  # slide the window right by one day
        one_back = current
    return one_back

Write the table version first. Shrink it only once it works, and only when you can name which cells the recurrence reads. You also lose the ability to walk back and list the chosen days, since the old cells are gone.

#The same shape, counting instead

The recurrence does not have to take a max. Suppose you climb a staircase of 6 steps and each stride covers 1, 2 or 3 steps. How many different stride sequences get you to the top?

State: ways[i] is the number of ways to stand on step i. Recurrence: your last stride came from step i − 1, i − 2 or i − 3, and those groups never overlap, so add them: ways[i] = ways[i − 1] + ways[i − 2] + ways[i − 3], skipping any index below 0. Base case: ways[0] = 1. Order: upward. Answer: ways[6].

function countClimbs(steps) {
  const ways = new Array(steps + 1).fill(0);
  ways[0] = 1; // standing at the bottom: one way, do nothing
  for (let i = 1; i <= steps; i++) {
    for (const stride of [1, 2, 3]) {
      if (i - stride >= 0) ways[i] += ways[i - stride];
    }
  }
  return ways[steps];
}
 
countClimbs(6); // 24

def count_climbs(steps):
    ways = [0] * (steps + 1)
    ways[0] = 1  # standing at the bottom: one way, do nothing
    for i in range(1, steps + 1):
        for stride in (1, 2, 3):
            if i - stride >= 0:
                ways[i] += ways[i - stride]
    return ways[steps]
 
count_climbs(6)  # 24

#Common mistakes

#Check yourself

#What to practise next

Practise both shapes: Sunny Orchard Row uses the no-two-in-a-row rule, and Stepping Stones Across the Pond counts ways. Then DP on Grids moves the same recipe into two dimensions, where each cell looks up and to the left.