### Present Remotely

Send the link below via email or IM

CopyPresent to your audience

Start remote presentation- Invited audience members
**will follow you**as you navigate and present - People invited to a presentation
**do not need a Prezi account** - This link expires
**10 minutes**after you close the presentation - A maximum of
**30 users**can follow your presentation - Learn more about this feature in our knowledge base article

# Dynamic programming: Three Basic Examples

No description

by

Tweet## Urairat Lertsripornchai

on 9 December 2012#### Transcript of Dynamic programming: Three Basic Examples

Example 1

Coin-row problem 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. Change-making problem Coin-collecting problem Several coins are placed in cells of an n×m board,

located in the upper left cell of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell.

On each step, the robot can move either one cell to

the right or one cell down from its current location. Dynamic programming is a technique for solving problems with overlapping subproblems. Typically, these subproblems arise from a recurrence relating a given problem’s solution to solutions of its smaller subproblems. Rather than solving overlapping subproblems again and again, dynamic programming suggests solving each of the smaller subproblems only once and recording the results in a table from

which a solution to the original problem can then be obtained. CSC210-24

Dynamic programming

Three Basic Examples How to do? Step : set up a recurrence relating a solution to a

larger instance to solutions of some

smaller instances

Step : solve smaller instances once

Step : record solutions in a table

Step : extract solution to the initial instance from

that table Invented by American mathematician Richard Bellman

in the 1950s to solve optimization problems and

later assimilated by CS

“Programming” here means “planning”

(not computer programming) Dynamic Programming Definition of Fibonacci numbers

F(n) = F(n-1) + F(n-2)

F(0) = 0

F(1) = 1

Computing the Fibonacci number recursively (top-down) Example: Fibonacci numbers The goal of this section is to introduce dynamic programming via three typical examples. Three Basic Examples The formula Algorithm Example solving the coin-row problem by dynamic programming for the coin row

5, 1, 2, 10, 6, 2 Give change for amount n using the minimum

number of coins of denominations . we consider a dynamic programming algorithm for the general case, assuming availability of unlimited quantities of coins for each of the m denominations The formula Example Algorithm Application of Algorithm MinCoinChange to amount n = 6 and coin denominations

1, 3, and 4. The formula Example Algorithm Step Step Step Step Step Step Step Step Step Step Step Step Step Coins to collect. Dynamic programming algorithm results. Two paths to collect 5 coins, the maximum number of coins possible. Given n items of

integer weights:

values:

a knapsack of integer capacity W

Find most valuable subset of the items that fit into the knapsack

Consider instance defined by first i items and capacity j (j W).

Let V[i,j] be optimal value of such instance. Then

Initial conditions: V[0,j] = 0 and V[i,0] = 0 Knapsack Problem by DP Knapsack Knapsack Problem by DP

(example) Example: Knapsack of capacity W = 5 Based on the slide prepared for the book: Anany Levitin, Introduction to the Design & Analysis of Algorithms, 3nd edition, Addison Weslay, 2007

Full transcriptCoin-row problem 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. Change-making problem Coin-collecting problem Several coins are placed in cells of an n×m board,

located in the upper left cell of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell.

On each step, the robot can move either one cell to

the right or one cell down from its current location. Dynamic programming is a technique for solving problems with overlapping subproblems. Typically, these subproblems arise from a recurrence relating a given problem’s solution to solutions of its smaller subproblems. Rather than solving overlapping subproblems again and again, dynamic programming suggests solving each of the smaller subproblems only once and recording the results in a table from

which a solution to the original problem can then be obtained. CSC210-24

Dynamic programming

Three Basic Examples How to do? Step : set up a recurrence relating a solution to a

larger instance to solutions of some

smaller instances

Step : solve smaller instances once

Step : record solutions in a table

Step : extract solution to the initial instance from

that table Invented by American mathematician Richard Bellman

in the 1950s to solve optimization problems and

later assimilated by CS

“Programming” here means “planning”

(not computer programming) Dynamic Programming Definition of Fibonacci numbers

F(n) = F(n-1) + F(n-2)

F(0) = 0

F(1) = 1

Computing the Fibonacci number recursively (top-down) Example: Fibonacci numbers The goal of this section is to introduce dynamic programming via three typical examples. Three Basic Examples The formula Algorithm Example solving the coin-row problem by dynamic programming for the coin row

5, 1, 2, 10, 6, 2 Give change for amount n using the minimum

number of coins of denominations . we consider a dynamic programming algorithm for the general case, assuming availability of unlimited quantities of coins for each of the m denominations The formula Example Algorithm Application of Algorithm MinCoinChange to amount n = 6 and coin denominations

1, 3, and 4. The formula Example Algorithm Step Step Step Step Step Step Step Step Step Step Step Step Step Coins to collect. Dynamic programming algorithm results. Two paths to collect 5 coins, the maximum number of coins possible. Given n items of

integer weights:

values:

a knapsack of integer capacity W

Find most valuable subset of the items that fit into the knapsack

Consider instance defined by first i items and capacity j (j W).

Let V[i,j] be optimal value of such instance. Then

Initial conditions: V[0,j] = 0 and V[i,0] = 0 Knapsack Problem by DP Knapsack Knapsack Problem by DP

(example) Example: Knapsack of capacity W = 5 Based on the slide prepared for the book: Anany Levitin, Introduction to the Design & Analysis of Algorithms, 3nd edition, Addison Weslay, 2007