Send the link below via email or IMCopy
Present to your audienceStart 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
Do you really want to delete this prezi?
Neither you, nor the coeditors you shared it with will be able to recover it again.
Make your likes visible on Facebook?
Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.
Dynamic programming: Three Basic Examples
Transcript of Dynamic programming: Three Basic Examples
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
Three Basic Examples How to do? Step : set up a recurrence relating a solution to a
larger instance to solutions of some
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
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