The goal of this section is to introduce dynamic programming via three typical examples.

**Three Basic Examples**

The goal of this section is
to introduce dynamic programming via three typical examples.

**EXAMPLE
1 ***Coin-row problem*** **There is a row of** n **coins whose values are some

Let ** F (n)** be the maximum amount that can be picked up
from the row of

We can compute ** F (n)** by filling the one-row table left to right in
the manner similar to the way it was done for the

**ALGORITHM** *CoinRow*** (C**[1

//Applies formula (8.3)
bottom up to find the maximum amount of money //that can be picked up from a
coin row without picking two adjacent coins //Input: Array ** C**[1

** F **[0]

** F **[

**return ***F*** **[** n**]

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. It is worth pointing

out that, in fact, we also
solved the problem for the first ** i** coins in the row given for
every 1 ≤

To find the coins with the
maximum total value found, we need to back-trace the computations to see which
of the two possibilities—*c***_{n}** +

Using the *CoinRow* to find ** F (n),** the largest amount of money that can be picked
up, as well as the coins composing an optimal set, clearly takes

**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

*d*_{1}* < d*_{2}* < *^{. . .}* < d*_{m}** **where

Let ** F (n)** be the minimum number of coins whose values
add up to

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

**ALGORITHM** *ChangeMaking*** (D**[1

//Applies dynamic programming
to find the minimum number of coins //of denominations *d*_{1} *<
d*_{2} *<*^{. . .}*< d***_{m}** where

//Input: Positive integer ** n** and array

** F **[0]

**for ***i*** **←** **1** to ***n*** do**

** t emp **← ∞;

**while ***j*** **≤** ***m*** and ***i*** **≥** **** D**[

** t emp **←

** F **[

The application of the
algorithm to amount ** n** = 6 and denominations 1, 3, 4 is shown in Figure
8.2. The answer it yields is two coins. The time and space efficiencies of the
algorithm are obviously

To find the coins of an
optimal solution, we need to backtrace the computa-tions to see which of the
denominations produced the minima in formula (8.4). For the instance
considered, the last application of the formula (for ** n** = 6

**EXAMPLE
3 ***Coin-collecting problem*** **Several coins are placed in
cells of an** n **×

Let ** F (i, j )** be the largest number of coins the robot can
collect and bring to the cell

where *c***_{ij}** = 1 if there is a coin in cell

Using these formulas, we can
fill in the ** n** ×

**ALGORITHM** *RobotCoinCollection*** (C**[1

//Applies dynamic programming
to compute the largest number of //coins a robot can collect on an ** n** ×

//Output: Largest number of
coins the robot can bring to cell *(n,
m)*** F **[1

** F **[

** F **[

The algorithm is illustrated
in Figure 8.3b for the coin setup in Figure 8.3a. Since computing the value of ** F (i, j )** by formula (8.5) for each cell of the table
takes constant time, the time efficiency of the algorithm is

Tracing the computations
backward makes it possible to get an optimal path: if ** F (i** − 1

**Exercises 8.1**

**
**What does dynamic programming have in common with
divide-and-conquer? What is a principal difference between them?

**
**Solve the instance 5, 1, 2, 10, 6 of the coin-row problem.

**
****a. **Show that the time efficiency
of solving the coin-row problem by straight-forward application of recurrence
(8.3) is exponential.

**
**Show that the time efficiency of solving the coin-row problem by
exhaustive search is at least exponential.

Apply the dynamic programming
algorithm to find all the solutions to the change-making problem for the
denominations 1, 3, 5 and the amount ** n **=

How would you modify the
dynamic programming algorithm for the coin-collecting problem if some cells on
the board are inaccessible for the robot? Apply your algorithm to the board
below, where the inaccessible cells are shown by X’s. How many optimal paths
are there for this board?

**
***Rod-cutting problem *Design a dynamic programming
algorithm for the fol-lowing problem. Find the maximum total sale price that
can be obtained by cutting a rod of ** n** units long into
integer-length pieces if the sale price of a piece

**
***Shortest-path counting *A chess rook can move
horizontally or vertically to* *any
square in the same row or in the same column of a chessboard. Find the number
of shortest paths by which a rook can move from one corner of a chessboard to the
diagonally opposite corner. The length of a path is measured by the number of
squares it passes through, including the first and the last squares. Solve the
problem

**
**by a dynamic programming algorithm.

**
**by using elementary combinatorics.

**
***Minimum-sum descent *Some positive integers are
arranged in an equilateral* *triangle
with ** n** numbers in its base like the
one shown in the figure below for

**
***Binomial coefficient *Design an efficient algorithm
for computing the bino-mial coefficient ** C(n, k)** that uses no multiplications. What are the
time and space efficiencies of your algorithm?

**
***Longest path in a dag*

**
**Design an efficient algorithm for finding the length of the longest
path in a dag. (This problem is important both as a prototype of many other
dynamic programming applications and in its own right because it determines the
minimal time needed for completing a project comprising precedence-constrained
tasks.)

**
**Show how to reduce the coin-row problem discussed in this section
to the problem of finding a longest path in a dag.

**
***Maximum square submatrix *Given an* **m** *×* **n** *boolean matrix* **B,** *find its* *largest square submatrix whose elements are all zeros. Design a
dynamic programming algorithm and indicate its time efficiency. (The algorithm
may be useful for, say, finding the largest free square area on a computer
screen or for selecting a construction site.)

**
***World Series odds *Consider two teams,* A *and* B*, playing a series of games*
*until one of the teams wins ** n** games. Assume that the
probability of

**
**Set up a recurrence relation for ** P (i, j )** that can be used by a dynamic programming algorithm.

**
**Find the probability of team *A*
winning a seven-game series if the proba-bility of it winning a game is 0.4.

**
**Write pseudocode of the dynamic programming algorithm for solving
this problem and determine its time and space efficiencies.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Dynamic Programming : Dynamic Programming: Three Basic Examples |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.