Data structures and algorithms 0/7

DSA, Dynamic programming

What is dynamic programming?

Also called DP

595 words · 3 min read

Dynamic programming (DP) solves a problem by solving smaller versions of the same problem first. Each smaller answer is worked out once and stored in a table, and the larger answers are built from the stored ones. The word "programming" in the name means planning by filling in a table, not writing code. The method is easiest to follow on an example, so we start with one.

Build the transition from the last jump

A frog crosses a row of stones. Each jump takes it to the next stone or to the one after that, and a jump costs the difference in height between the two stones. We want the cheapest way to get from the first stone to the last. In the first sample the heights are 10, 30, 40 and 20. We'll number the stones from 0, the way list positions are numbered, so the frog starts on stone 0 and has to reach stone 3. It has three routes:

  • 0→1→2→30 \to 1 \to 2 \to 3 costs 20+10+20=5020 + 10 + 20 = 50.
  • 0→1→30 \to 1 \to 3 costs 20+10=3020 + 10 = 30.
  • 0→2→30 \to 2 \to 3 costs 30+20=5030 + 20 = 50.

The cheapest costs 30, which is the expected output. A program could find the answer the same way, by listing every route and keeping the cheapest, but the number of routes grows too fast. Every route to a stone comes from one of the two stones before it, so a stone's count of routes is the sum of those two stones' counts. Stones 0 and 1 have one route each, and from there the counts run 1, 1, 2, 3, 5, 8, 13: the Fibonacci numbers. Fifty stones have 12,586,269,025 routes to the last one. At the problem's limit of 10510^5 stones, the number of routes has 20,899 digits.

Listing routes repeats work: every route through stone 2 starts with a route to stone 2, whose cost is added up again for every way of continuing from stone 2. One question per stone is enough: what is the cheapest cost of reaching stone ii? Call the answer dp[i]. The last jump of a route to stone ii starts on stone i−1i - 1 or stone i−2i - 2. If it starts on stone i−1i - 1, the cheapest such route reaches that stone for dp[i - 1] and then pays ∣hi−hi−1∣|h_i - h_{i-1}| for the jump, where hih_i is the height of stone ii. The same goes for stone i−2i - 2. That gives one candidate for each possible last jump, and dp[i] is the smaller:

dp[i]=min⁡{dp[i−1]+∣hi−hi−1∣dp[i−2]+∣hi−hi−2∣\texttt{dp}[i] = \min \begin{cases} \texttt{dp}[i-1] + |h_i - h_{i-1}| \\ \texttt{dp}[i-2] + |h_i - h_{i-2}| \end{cases}

A rule like this is called a transition: it computes the value for one stone from the values for earlier stones. It uses only the cheapest way of reaching stone i−1i - 1 and forgets the others, because the jumps still ahead do not depend on how the frog got there. Two routes that reach stone i−1i - 1 with different totals face the same jumps at the same prices, so whatever the frog does next adds the same amount to either, and the more expensive arrival cannot finish cheaper.

The first sample drawn as stones and jumps, each arrow labelled with its cost. Stone 3 has two arrows into it, one for each line of the transition.

Here is the table for the sample, filled from left to right. dp[0] is 0 and dp[1] is 20. Stone 2 compares arriving from stone 1 with arriving from stone 0, and stone 3 compares arriving from stone 2 with arriving from stone 1:

dp[2]=min⁡(20+10, 0+30)=30dp[3]=min⁡(30+20, 20+10)=30\begin{aligned} \texttt{dp}[2] &= \min(20 + 10,\ 0 + 30) = 30 \\ \texttt{dp}[3] &= \min(30 + 20,\ 20 + 10) = 30 \end{aligned}

The finished table is [0, 20, 30, 30]. Its last entry, 30, is the answer, the cost of the cheapest route we listed. This time it took at most one comparison per stone, and we never wrote out a whole route.

DP fundamentals: states and transitions State what each table entry means, build the transition from the last choice, and fill the table in an order where every entry it reads is ready. Read the full lesson