Dynamic programming 0/49

DP fundamentals: states and transitions · 1 of 3

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.

3,693 words · 17 min read

Part 1 of 9 Dynamic programming

Dynamic programming and the frog problem

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.

There are NN stones in a row, and stone ii has height hih_i. A frog starts on the first stone and wants to reach the last one. From any stone it can jump to the next stone or to the one after that, and a jump between stones of heights aa and bb costs ∣a−b∣|a - b|.

The first input line holds NN and the second the NN heights. Print the minimum total cost of reaching the last stone.

Constraints

  • 2≤N≤1052 \le N \le 10^5
  • 1≤hi≤1041 \le h_i \le 10^4

Sample 1 · Input

4
10 30 40 20

Output

30

Sample 2 · Input

2
10 10

Output

0

Sample 3 · Input

6
30 10 60 10 60 50

Output

40

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.