Scribd
Upload
3 views2 pages

Cleaned Dynamic Programming Notes

The document presents three examples of dynamic programming problems: the Coin Row Problem, Change Making Problem, and Coin Collecting Problem. Each example includes a recurrence relation, algorithm, and a sample calculation to illustrate how to find optimal solutions. The algorithms demonstrate how to maximize coin collection or minimize the number of coins used based on given constraints.

Uploaded by

pallavi.bsmh
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views2 pages

Cleaned Dynamic Programming Notes

The document presents three examples of dynamic programming problems: the Coin Row Problem, Change Making Problem, and Coin Collecting Problem. Each example includes a recurrence relation, algorithm, and a sample calculation to illustrate how to find optimal solutions. The algorithms demonstrate how to maximize coin collection or minimize the number of coins used based on given constraints.

Uploaded by

pallavi.bsmh
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Dynamic Programming – Three Basic Examples

Example 1 – Coin Row Problem


There is a row of n coins whose values are integers c1, c2, … cn. The goal is to pick up the maximum amount of
money subject to the constraint that no two adjacent coins can be picked. Let F(n) be the maximum amount that can
be picked from n coins. Recurrence Relation: F(n) = max { cn + F(n−2), F(n−1) }, for n ≥ 1 Base Conditions: F(0) = 0
F(1) = c1
ALGORITHM COINROW(c[1..n])

Input : Array c[1..n] of positive integers indicating coin values


Output: Maximum amount of money that can be picked

F[0] = 0
F[1] = c[1]

for i = 2 to n do
F[i] = max(c[i] + F[i−2], F[i−1])

return F[n]

Example: C = [5, 1, 2, 10, 6, 2]


Index 1 2 3 4 5 6
Coin Value 5 1 2 10 6 2

F[0] = 0, F[1] = 5

F[2] = max(1 + 0, 5) = 5
F[3] = max(2 + 5, 5) = 7
F[4] = max(10 + 5, 7) = 15
F[5] = max(6 + 7, 15) = 15
F[6] = max(2 + 15, 15) = 17

Optimal set of coins: {5, 10, 2}

Example 2 – Change Making Problem


Given a change for amount n using minimum number of coins of denominations d1 < d2 < … < dm, dynamic
programming can be used assuming unlimited availability of each denomination. Let F(n) be the minimum number of
coins whose values add up to n. Recurrence Relation: F(n) = min { F(n − dj) } + 1 Base Condition: F(0) = 0
ALGORITHM ChangeMaking(D[1..m], n)

Input : Integer n and array D[1..m]


Output: Minimum number of coins that add up to n

F[0] = 0

for i = 1 to n do
temp = infinity
j = 1
while j <= m and i >= D[j] do
temp = min(F[i - D[j]], temp)
j = j + 1

F[i] = temp + 1

return F[n]

Example: Denominations = [1, 3, 4], Amount = 6


F[1] = 1
F[2] = 2
F[3] = 1
F[4] = 1
F[5] = 2
F[6] = 2

Optimal set of coins: {3, 3}


Index 0 1 2 3 4 5 6
F Table 0 1 2 1 1 2 2

Example 3 – Coin Collecting Problem


Dynamic programming can compute the largest number of coins a robot can collect on an n × m board by starting at
the upper-left corner and moving only right or down to reach the bottom-right corner. Input: Matrix C[1..n, 1..m] whose
elements are either 0 or 1. Output: Largest number of coins that a robot can collect.
ALGORITHM RobotCoinCollection(C[1..n, 1..m])

F[1,1] = C[1,1]

for j = 2 to m do
F[1,j] = F[1,j−1] + C[1,j]

for i = 2 to n do
F[i,1] = F[i−1,1] + C[i,1]

for i = 2 to n do
for j = 2 to m do
F[i,j] = max(F[i−1,j], F[i,j−1]) + C[i,j]

return F[n,m]

The robot traces the optimal path from the top-left to the bottom-right corner while collecting the maximum number of
coins.

Prepared neatly from the uploaded handwritten PDF notes.

You might also like