Three basic examples

At every step, we decide using answers from smaller subproblems.

DP is simply storing the best answers already computed to avoid doing the same
work twice. It’s like keeping a "cheat sheet" as you go.

Example A: The Coin Row (The Greedy Trap)

The Goal: There is a row of n coins whose values are some positive integers
c₁, c₂,...,cn, not necessarily distinct. The goal is to pick up the maximum amount of
money subject to the constraint that no two coins adjacent in the initial row can be
picked up.
The Logic: For every coin, you have two choices:
Pick it: You get its value plus the best total from two spots back (C[i] + F[i-2]).
The Visual: Show a table filling left-to-right.
E.g. 5, 1, 2, 10, 6, 2. What is the best selection?
 Three basic examples
Example B: Change-Making (The Efficiency Strategy)
The Goal: Give a specific amount of change using the minimum number of coins possible
The Logic: To find the best way to make change for n, look at the best way to make change
for (n - each coin value) and just add 1.
The Lesson: This shows how DP can find an optimal minimum by comparing all available
choices at each step. This problem shifts the goal from "maximum value" to
"minimum quantity" using unlimited supplies of denominations.

Example C: The Robot Collector (The 2D Grid)

The Goal: A robot starts at the top-left of a grid and must reach the bottom-right, collecting
as many coins as possible.
The Rule: The robot can only move Right or Down.
The Logic: The best way to reach any cell (i, j) is the maximum of the cell above it or the cell
to its left, plus whatever coin is in the current cell.
The Visual: This introduces a two-dimensional table, filling it row-by-row or column-by-
column. This expands DP into two dimensions, which is common in pathfinding and
Three basic examples
 Three basic examples

The application of the algorithm to the coin row of denominations 5, 1, 2, 10, 6, 2 is

shown in Figure 8.1. It yields the maximum amount of 17.
Three basic examples
Three basic examples
➢ To find the coins with the maximum total value found, we need to backtrace the
computations to see which of the two possibilities—cn + F(n − 2) or F(n − 1)
➢ In the last application of the formula, it was the sum c6 + F(4), which means that the
coin c6 = 2 is a part of an optimal solution.
➢ Moving to computing F(4), the maximum was produced by the sum c4 + F(2), which
means that the coin c4 = 10 is a part of an optimal solution as well.
➢ Finally, the maximum in computing F(2) was produced by F(1), implying that the
coin c2 is not the part of an optimal solution and the coin c1= 5 is.
➢ Thus, the optimal solution is {c1, c4, c6}. To avoid repeating the same computations
during the backtracking, the information about which of the two terms in (8.3) was
larger can be recorded in an extra array when the values of F are computed.
➢ Solve the instance 5, 1, 2, 10, 6 of the coin-row problem.
Three basic examples
Initialize:
𝐹 0 =0
𝐹 1 =5
Now compute sequentially.
For coin 2 (value = 1)
𝐹 2 = max 𝐹 1 𝐹 0 + 1
𝐹 2 = max 5 0 + 1 = 5
For coin 3 (value = 2)
𝐹 3 = max 𝐹 2 𝐹 1 + 2
𝐹 3 = max 5 5 + 2 = 7
For coin 4 (value = 10)
𝐹 4 = max 𝐹 3 𝐹 2 + 10
𝐹 4 = max 7 5 + 10 = 15
For coin 5 (value = 6)
𝐹 5 = max 𝐹 4 𝐹 3 + 6
𝐹 5 = max 15 7 + 6 = 15
Three basic examples
➢ EXAMPLE 2 Change-making problem Consider the general instance of the following well-known
problem. Give change for amount n using the minimum number of coins of denominations d1<d2 < . .
.<dm.
➢ For the coin denominations used in the United States, as for those used in most if not all other countries,
there is a very simple and efficient algorithm discussed in the next chapter.
➢ Here, we consider a dynamic programming algorithm for the general case, assuming availability of
unlimited quantities of coins for each of the m denominations d1< d2 < . . . < dm where d1 = 1.
➢ Let F(n) be the minimum number of coins whose values add up to n; it is convenient to define F(0) = 0.
The amount n can only be obtained by adding one coin of denomination dj to the amount n − dj for j = 1,
2, . . . , m such that n ≥ dj .
➢ Therefore, we can consider all such denominations and select the one minimizing F(n − dj ) + 1. Since 1
is a constant, we can, of course, find the smallest F(n − dj ) first and then add 1 to it.
➢ Hence, we have the following recurrence for F(n):

➢ We can compute F(n) by filling a one-row table left to right in the manner similar to the way it was done
above for the coin-row problem, but computing a table entry here requires finding the minimum of up to
Three basic examples
Three basic examples
Possible ways to make 6 are:
1 + 1 + 1 + 1 + 1 + 1 = 6→ 6 coins
3 + 3 = 6→ 2 coins
4 + 1 + 1 = 6→ 3 coins
3 + 1 + 1 + 1 = 6→ 4 coins
Now choose the minimum number of coins.
So the best answer is:
6=3+3
using only 2 coins.
Therefore:
𝐹 6 =2
Three basic examples
n Meaning of F[n] Value

F[0] minimum coins to make amount 0 0

F[1] minimum coins to make amount 1 1

F[2] minimum coins to make amount 2 2

F[3] minimum coins to make amount 3 1

F[4] minimum coins to make amount 4 1

F[5] minimum coins to make amount 5 2

F[6] minimum coins to make amount 6 2

Three basic examples
Three basic examples
Step 1: Amount = 1
Possible coin:
•use coin 1
Then:
𝐹 1 =𝐹 1−1 +1
=𝐹 0 +1
=0+1=1
Meaning:
•To make amount 1, we use one coin: {1}
Three basic examples
Step 2: Amount = 2
Only coin 1 works.
𝐹 2 =𝐹 2−1 +1
=𝐹 1 +1
=1+1=2
Meaning:
2=1+1
needs 2 coins
 Three basic examples
Step 3: Amount = 3
Possible coins:
•1
•3
Now check both possibilities.
Using coin 1
𝐹 3−1 +1=𝐹 2 +1=2+1=3
Using coin 3
𝐹 3−3 +1=𝐹 0 +1=0+1=1
Take minimum:
min 3 1 = 1
So:
𝐹 3 =1
Meaning:
•Best way is directly using coin 3.
 Three basic examples
Step 4: Amount = 4
Possible coins:
1
3
4
Check all.
Using 1
𝐹 4−1 +1=𝐹 3 +1=1+1=2
Using 3
𝐹 4−3 +1=𝐹 1 +1=1+1=2
Using 4
𝐹 4−4 +1=𝐹 0 +1=0+1=1
Take minimum:
min 2 2 1 = 1
So:
𝐹 4 =1
Best way:
one coin {4}
 Three basic examples
Step 5: Amount = 5
Possible coins:
1
3
4
Using 1
𝐹 5−1 +1=𝐹 4 +1=1+1=2
Using 3
𝐹 5−3 +1=𝐹 2 +1=2+1=3
Using 4
𝐹 5−4 +1=𝐹 1 +1=1+1=2
Take minimum:
min 2 3 2 = 2
So:
𝐹 5 =2
Possible optimal ways:
4+1
1+4
 Three basic examples
Step 6: Amount = 6
Possible coins:
1
3
4
Using 1
𝐹 6−1 +1=𝐹 5 +1=2+1=3
Using 3
𝐹 6−3 +1=𝐹 3 +1=1+1=2
Using 4
𝐹 6−4 +1=𝐹 2 +1=2+1=3
Take minimum:
min 3 2 3 = 2
So:
𝐹 6 =2
Best solution:
3+3
Three basic examples

Amount n 0 1 2 3 4 5 6

F[n] 0 1 2 1 1 2 2