Hard Problemsminimizationlinear

Program for Bridge and Torch problem

A group of people, each with a different crossing speed, must get across a bridge at night sharing one torch; at most two people can cross together and they move at the slower one's pace, and the torch must be carried back for anyone else to cross. Find the minimum total time for everyone to reach the other side.

Note. This problem is typically solved with a greedy argument about the two fastest and two slowest crossers; the DP formulation shown here is the derivable, table-based alternative.

Do this lesson first: coin change

Example input

crossing times 1, 2, 5, 8, 13, 20, 25, 30 minutes

Expected output

75

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i] = min(dp[i-1] + t[0] + t[i-1], dp[i-2] + t[0] + 2*t[1] + t[i-1])

Ask how the slowest person still on this side gets over. Either they cross paired with the fastest, who then walks the torch back, which costs t[i-1] for the crossing and t[0] for the return on top of solving the smaller group, or the two slowest cross together and the two fastest handle the torch around them: the fastest pair goes over, the fastest returns, the slow pair crosses at t[i-1], and the second fastest returns. That second option counts only one of the two slow times, which is what makes it win once the slow people are far apart from the fast ones.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0] = 0, nobody to move. dp[1] = t[0], one person walks across alone. dp[2] = t[1], two people cross together at the slower one's pace, and nobody has to come back. Fill upward from i = 3, since both options read strictly smaller counts. The sort is not a convenience here, it is what makes t[0] and t[1] mean the fastest and second fastest at every step, which both options depend on.

i=0

i=1

i=2

i=3

i=4

i=5

i=6

i=7

i=8

0

1

2

8

15

26

40

56

75

bridge-and-torch.ts

1function crossBridge(times) {
2 const t = [...times].sort((a, b) => a - b);
3 const dp = [0, t[0], t[1]];
4 for (let i = 3; i <= t.length; i++) {
5 const ferry = dp[i - 1] + t[0] + t[i - 1];
6 const shuttle =
7 dp[i - 2] + t[0] + 2 * t[1] + t[i - 1];
8 dp[i] = Math.min(ferry, shuttle);
9 }
10 return dp[t.length];
11}

Base caseComputedBeing readAnswer

The code, the trap, the variations

bridge-and-torch.ts

1function crossBridge(times) {
2 const t = [...times].sort((a, b) => a - b);
3 const dp = [0, t[0], t[1]];
4 for (let i = 3; i <= t.length; i++) {
5 const ferry = dp[i - 1] + t[0] + t[i - 1];
6 const shuttle =
7 dp[i - 2] + t[0] + 2 * t[1] + t[i - 1];
8 dp[i] = Math.min(ferry, shuttle);
9 }
10 return dp[t.length];
11}

Where people go wrong

Assuming the fastest person should always carry the torch back. It is the obvious rule and it is wrong exactly when the two slowest are much slower than the two fastest, because pairing the slow people makes one of their times disappear entirely, and that saving outweighs the extra return trip. dp[3] = 8 and dp[4] = 15 in this table are the two options trading places. The other trap is forgetting to sort, which quietly breaks t[0] and t[1] and therefore both options at once.

Three people may cross at once instead of two.
A third option joins the min, built the same way from the three slowest. The state is still a count, so the table keeps its shape; only the number of candidates per cell grows.
The torch runs out after a fixed number of minutes.
Nothing changes in the recurrence. Compute dp[n] and compare it against the limit, since the recurrence already gives the minimum, and no schedule can beat it.

The painter's partition problem Matrix Chain Multiplication