One-dimensional dynamic programming

When to use it

Use it when the answer at position i of one list depends only on the answers at a few earlier positions, so one row of cells is enough.

It belongs to the optimization group: Find the best answer without trying every possibility: reuse smaller answers, or take the safe choice first.

Watch it work

A pool sells a single ticket for one day and a triple ticket for three days in a row, at the given prices. The list has 1 for a day you swim and 0 for a day you do not. Return the fewest coins that pay for every swim day.

Input
swim = [1, 0, 1, 1, 1, 0, 1]
single = 2
triple = 5

Output
9

The method

1. Make one cell for each number of days: no days cost 0
2. Fill the cells left to right, one more day each time
3. No swim on the new day: copy the cell before
4. Swim day: the cheaper of a single and a triple ticket
5. Return the last cell, which covers every day

The run, one moment at a time

1. Step 1. Cell i of cost will hold the fewest coins for the first i days. No days cost 0, so cell 0 is known. The cells with ? are worked out next.

   swim: 1 0 1 1 1 0 1
   cost: 0 ? ? ? ? ? ? ?
   

2. Step 2. Go left to right. Cell 1 is next: it covers the first day, which is swim[0]. Every cell reads only cells on its left, which are already final.

   swim: 1 0 1 1 1 0 1
   cost: 0 ? ? ? ? ? ? ?
   

3. Step 4. Swim day. Single ticket added to cell 0: 0 + 2 = 2. Triple ticket added to cell 0: 0 + 5 = 5. The single is cheaper: cell 1 gets 2.

   swim: 1 0 1 1 1 0 1
   cost: 0 2 ? ? ? ? ? ?
   

4. Step 3. No swim on the new day, so nothing more is paid. Cell 2 copies cell 1: 2.

   swim: 1 0 1 1 1 0 1
   cost: 0 2 2 ? ? ? ? ?
   

5. Step 4. Swim day. Single ticket added to cell 2: 2 + 2 = 4. Triple ticket for the last three days, added to cell 0: 0 + 5 = 5. The single is cheaper: cell 3 gets 4.

   swim: 1 0 1 1 1 0 1
   cost: 0 2 2 4 ? ? ? ?
   

6. Step 4. Swim day. Single ticket added to cell 3: 4 + 2 = 6. Triple ticket for the last three days, added to cell 1: 2 + 5 = 7. The single is cheaper: cell 4 gets 6.

   swim: 1 0 1 1 1 0 1
   cost: 0 2 2 4 6 ? ? ?
   

7. Step 4. Swim day. Single ticket added to cell 4: 6 + 2 = 8. Triple ticket for the last three days, added to cell 2: 2 + 5 = 7. The triple is cheaper: cell 5 gets 7.

   swim: 1 0 1 1 1 0 1
   cost: 0 2 2 4 6 7 ? ?
   

8. Step 3. No swim on the new day, so nothing more is paid. Cell 6 copies cell 5: 7.

   swim: 1 0 1 1 1 0 1
   cost: 0 2 2 4 6 7 7 ?
   

9. Step 4. Swim day. Single ticket added to cell 6: 7 + 2 = 9. Triple ticket for the last three days, added to cell 4: 6 + 5 = 11. The single is cheaper: cell 7 gets 9.

   swim: 1 0 1 1 1 0 1
   cost: 0 2 2 4 6 7 7 9
   

10. Step 5. Cell 7 covers all 7 days, so the answer is 9: a single, a triple and a single ticket, 2 + 5 + 2. Only single tickets would cost 10.

    swim: 1 0 1 1 1 0 1
    cost: 0 2 2 4 6 7 7 9
    

The code

The numbered comments are the steps of the method.

function solve(swim, single, triple) {
  // 1. Make one cell for each number of days: no days cost 0
  const cost = Array(swim.length + 1).fill(0);
  // 2. Fill the cells left to right, one more day each time
  for (let i = 1; i <= swim.length; i++) {
    // 3. No swim on the new day: copy the cell before
    if (swim[i - 1] === 0) {
      cost[i] = cost[i - 1];
      continue;
    }
    // 4. Swim day: the cheaper of a single and a triple ticket
    const one = cost[i - 1] + single;
    // A triple ticket pays for this day and the two days before it.
    const three = cost[Math.max(i - 3, 0)] + triple;
    cost[i] = Math.min(one, three);
  }
  // 5. Return the last cell, which covers every day
  return cost[swim.length];
}

def solve(swim, single, triple):
    # 1. Make one cell for each number of days: no days cost 0
    cost = [0] * (len(swim) + 1)
    # 2. Fill the cells left to right, one more day each time
    for i in range(1, len(swim) + 1):
        # 3. No swim on the new day: copy the cell before
        if swim[i - 1] == 0:
            cost[i] = cost[i - 1]
            continue
        # 4. Swim day: the cheaper of a single and a triple ticket
        one = cost[i - 1] + single
        # A triple ticket pays for this day and the two days before it.
        three = cost[max(i - 3, 0)] + triple
        cost[i] = min(one, three)
    # 5. Return the last cell, which covers every day
    return cost[len(swim)]

How to spot it

Asked: Count the ways to reach the end, or say if there is any way

You are asked how many or whether, not which. The answer for a position comes from the answers for the positions one move before it.

Asked: The largest or smallest total you can get along a row

The best total up to a position is built from the best totals a few positions earlier. Each is worked out once and read later.

Given: Taking one item changes which later items you may take

No choice is safe on the spot, so both sides of every choice are compared. The cells keep that from repeating work.

Limits: Up to 100 items, and each one is a yes or no choice

Trying every mix of choices is 2 to the power 100, far too many. One cell for each position is about 100 cells.

Looks like it, but is not

• At every step one choice is safe: once taken, it never has to be taken back. Use Greedy choice. Then no table is needed. Dynamic programming is for tasks where the choice that looks best now can turn out worse later.
• The task wants every possible arrangement listed, and the input has about 10 items. Use Backtracking. A row of cells can count the arrangements or find the best one. To list them all, each must be built, one choice at a time.
• Each item is taken or left, and the taken items must fit a budget or reach an exact total. Use Knapsack dynamic programming. The position is not enough there, because what can still be taken depends on the amount used. The cells are numbered by amount.

Cost and mistakes

Time is about n steps, written O(n): each cell is filled once from a few earlier cells. Extra space is the row of cells, also O(n). If a cell reads only the last few cells, a few variables can replace the row.

Watch out

• Before any code, say in one sentence what a cell means. Here: cost[i] is the fewest coins for the first i days. Every line of the code follows from that sentence.
• The row has one cell more than the list, because cell 0 is the answer for no days at all. So cost[i] goes with swim[i - 1], not with swim[i].

In the 150

9 problems of the 150 use it. Naming them gives their method away, so the list is folded.