Skip to content
Tutorials Center
My learning

Topics

Lesson 161 of 225 ยท Dynamic Programming

Optimal Game Strategy, Painter's Partition and Bridge and Torch

Solve three classic DP puzzles in Python: the coin-row game with optimal players, painter's partition by DP, and the bridge-and-torch crossing problem.

Some dynamic programs do not look like "fill a table of counts". They hide a decision maker: an opponent who also plays well, a limited number of workers, or a group of people who must cross a bridge. In this lesson you will meet three of them. The coin-row game is an interval DP that models two players. Painter's partition is a DP where the number of groups is part of the state. Bridge and torch is a small puzzle whose DP has only one dimension but a clever two-way transition.

You should be comfortable with interval DP, 1D DP and prefix sums.

The coin-row game

Problem. A row of coins with values a[0..n-1] lies on a table. Two players, you and a friend, alternate turns. On each turn the player must take one coin from either end of the row. You move first and both of you play perfectly. What is the largest total you can guarantee?

A greedy rule such as "always take the bigger end" fails. For [4, 42, 5, 1] the bigger end is 4, but taking it exposes the 42 to your friend. You need to look ahead, and the cleanest way to do that is to track a score difference instead of two separate totals.

State as a score difference

Let diff[i][j] be the best value of (current player's total) minus (opponent's total) when only the coins a[i..j] remain and it is the current player's turn.

  • If the current player takes a[i], they gain a[i], and then the opponent becomes the "current player" on a[i+1..j] with advantage diff[i+1][j]. From our point of view that advantage counts against us: a[i] - diff[i+1][j].
  • If they take a[j], the value is a[j] - diff[i][j-1].
TEXT
diff[i][j] = max(a[i] - diff[i+1][j], a[j] - diff[i][j-1])
diff[i][i] = a[i]

The table is filled by increasing interval length, exactly like the interval DP template. Once you have diff[0][n-1], the first player's total is (sum + diff) / 2, because mine + theirs = sum and mine - theirs = diff.

Python Coin-row game: DP and brute-force minimax

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For [4, 42, 5, 1] the first player ends with 43 and the opponent with 9 (a margin of 34): taking the 1 first leaves the 4 and 42 on the ends, and the opponent cannot take the 42 without handing you the other end first. Greed (taking the 4) would have lost. The brute-force margin must equal first - second. Whenever the number of coins is even, the first player can always at least tie, because they can choose to take all the coins at even positions or all at odd positions.

The memoized minimax above is itself a valid DP (top-down), and for short rows it is the easiest version to get right. Write it first, then convert it to the table if you need speed. See memoization versus tabulation.

Counting and complexity

There are O(n^2) intervals and each costs O(1), so time is O(n^2) and space is O(n^2). Because diff[i][j] only needs the previous length, you can reduce space to O(n) with a single rolling row, as the next example shows.

Python Space-saving version and a larger test

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the update row[i] = max(coins[i] - row[i + 1], coins[j] - row[i]). On the right side, row[i + 1] is the old value for interval (i+1, j) and row[i] is the old value for (i, j-1). Reading before writing in increasing i order is what makes the single row safe.

Painter's partition

Problem. You have n boards with lengths a[0..n-1] in a fixed order, and k painters. Each painter paints a contiguous block of boards, and painting a board of length L takes L time units. All painters work at the same time. What is the smallest possible finishing time?

This is the same question as "split an array into k parts and minimize the largest part sum". In binary search on the answer you solved it by guessing the time. Here is the dynamic programming view, which is slower but extends to cost functions that are not monotone.

State. dp[p][i] = the minimum possible finishing time when the first i boards are painted by p painters.

Transition. The last painter takes boards j..i-1 for some j. The finishing time is the larger of the earlier painters' time and this painter's block sum:

TEXT
dp[p][i] = min over j in [p-1, i-1] of max( dp[p-1][j], prefix[i] - prefix[j] )
dp[1][i] = prefix[i]
Python Painter's partition by DP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The time is O(k * n^2) and the space O(k * n). With prefix sums each block sum is O(1). When dp[p-1][j] grows with j and the block sum shrinks with j, the best j sits where the two lines cross, so you can speed up the inner loop with binary search or a monotone pointer. In practice, for large inputs you use binary search on the answer instead: O(n log(sum)).

Use the DP when the cost of a block is something other than a plain sum, for example "sum squared" or "sum plus a fixed setup cost". Binary search on the answer only works when the cost is monotone in a way you can test with a yes/no check. The DP works for any cost you can compute from (j, i).

Bridge and torch

Problem. n people must cross a narrow bridge at night. They have one torch, and the bridge carries at most two people at a time. Person i needs t[i] minutes to cross, and a pair moves at the speed of the slower person. The torch must be carried back for the next group. What is the minimum total time to get everyone across?

Sort the times so that t[0] <= t[1] <= ... <= t[n-1]. The fastest person is a natural torch courier. Consider the two slowest people, t[n-1] and t[n-2]. There are two sensible ways to get them over:

  1. Fastest escorts each slow person. The fastest crosses with the slowest (t[n-1]), returns (t[0]), crosses with the next slowest (t[n-2]), returns (t[0]). Cost: 2*t[0] + t[n-1] + t[n-2].
  2. The two fastest shuttle. The two fastest cross (t[1]), the fastest returns (t[0]), the two slowest cross together (t[n-1]), the second fastest returns (t[1]). Cost: t[0] + 2*t[1] + t[n-1].

After either plan, the two slowest are across and the torch is back with the others, leaving a smaller problem with n - 2 people.

TEXT
f(n) = min( f(n-2) + 2*t[0] + t[n-1] + t[n-2],     # plan 1
            f(n-2) + t[0] + 2*t[1] + t[n-1] )      # plan 2
f(1) = t[0],   f(2) = t[1],   f(3) = t[0] + t[1] + t[2]
Python Bridge and torch: DP versus exhaustive search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The classic instance [1, 2, 5, 10] takes 17 minutes: 1 and 2 cross (2), 1 returns (1), 5 and 10 cross (10), 2 returns (2), 1 and 2 cross (2). Note that the greedy idea "always send the fastest with the next person" gives 19 here.

The DP is O(n log n) for sorting plus O(n) for the table. The exhaustive search, by contrast, explores every state (who is on the far side, where the torch is), about 2^n * 2 of them, which is why it is only used to double-check the formula on small inputs.

Common mistakes

  • Tracking two totals in the coin game. Keeping mine and theirs separately works but doubles the bookkeeping. The difference form has one number per state and one max.
  • Forgetting the sign flip. After you move, the opponent is the current player, so their advantage is subtracted.
  • Allowing empty blocks in painter's partition. Each painter must have at least one board, so j starts at p - 1.
  • Leaving the input unsorted in bridge and torch. The two-plan recurrence assumes sorted times.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the coin-row game, what does diff[i][j] represent?

    The current player's advantage on the remaining interval. The recurrence subtracts the opponent's advantage after the move, because roles swap.
  2. 2. If the total of all coins is 60 and the first player's optimal margin is 10, what does the first player collect?

    mine + theirs = 60 and mine - theirs = 10, so mine = (60 + 10) / 2 = 35.
  3. 3. In painter's partition DP, why does the last painter's block start at j >= p - 1?

    dp[p-1][j] needs at least p - 1 boards to give every earlier painter something to paint.
  4. 4. For times [1, 2, 5, 10], which crossing plan is best for the two slowest people?

    Plan 2 costs 1 + 22 + 10 = 15 for that step versus 21 + 10 + 5 = 17 for plan 1, and the leftover problem is smaller.

Summary

  • A two-player optimal game on an interval is solved with diff[i][j] = max(a[i] - diff[i+1][j], a[j] - diff[i][j-1]); the first player's total is (sum + diff) / 2.
  • Painter's partition (split into k contiguous blocks, minimize the largest sum) is dp[p][i] = min over j of max(dp[p-1][j], block(j, i)) in O(k n^2).
  • Binary search on the answer is faster for plain sums; the DP is the tool for general block costs.
  • Bridge and torch: sort, then f(n) is the better of two plans for the two slowest people; check small cases by exhaustive search.

Next: Weighted Job Scheduling and Largest Divisible Subset, where DP meets binary search.