Competitive Programming (0907548)

Dynamic Programming

Instructor: Dr. Fahed Jubair

Computer Engineering Department
University of Jordan
 Definition
• Dynamic Programming (DP) is a technique used to solve
problems by breaking them down into smaller, overlapping
subproblems.

• DP is often used for optimization problems over recursion

• To avoid redundancy in computation, DP stores solutions of sub-

problems in a data structure (e.g., in a table) and reuses them,
optimizing performance.

© All Right Reserved

 0-1 Knapsack
Problem Statement
• Given 𝑛 items, each with its own value Vi and weight Wi , ∀i ∈ [0..n-1],
and a maximum knapsack size S, compute the maximum value of the
items that we can carry?

• Example:
values = {100, 70, 50, 10}
weights = {10, 4, 6, 12}
S = 12
Optimal answer is to carry item 1 and item 2 à max value is 120

• How to solve this optimization problem?

© All Right Reserved

 0-1 Knapsack
Solution Strategies
• Solution #1: complete search works but expensive
Ø Generate all possible subsets, and find the subset of items
that can fit in the knapsack and yield maximum value

• Solution #2: greedy fails

Ø Sort the items by their value and fill the knapsack starting
with the item that has the highest value
Ø Sort the items by their weight and fill the knapsack starting
with the item that has the lowest weight
Ø Sort the items by their value/weight ratio and fill the
knapsack starting with the item that has the highest ratio

It is possible to come up with numerical

• Solution #3: DP! (see next slide) examples that show that greedy stratigies
will fail getting the optimal answer
© All Right Reserved
 0-1 Knapsack
DP Solution
• For each item k, there are only two possibilities:
Ø Item k is part of the optimal answer (i.e., take the item)
Ø Item k is not part of the optimal answer (i.e., leave the item)
• Thus, the optimal answer can be found by trying both
possibilities and determining which possibility gives the
maximum value!
• Let val(k,remW) be a recursive function that calculates the
maximum value, where k is the index of the current item and
remW is the remaining weight in the knapsack

val(k,remW) = max ( value[k] + val(k+1, remW – weight[k]) , val(k+1, remW ) )

Take the item Leave the item

© All Right Reserved
 0-1 Knapsack
DP Implementation

© All Right Reserved

0-1 Knapsack
Memorization

© All Right Reserved

 The Coin Change Problem
Problem Statement
• Suppose that we are given a set of k coins {c1, c2, ..., ck} and a target
sum of money n, and we are asked to construct the sum n using as
few coins as possible. There are no restrictions on how many times
we can use each coin value.

• Example:
coins = {1, 2, 5}
n = 12
Optimal answer is 3 coins (2 + 5 + 5)

• How to solve this optimization problem?

© All Right Reserved

 The Coin Change Problem
Solution Strategies
• Solution #1: complete search works but expensive
Ø Generate all possible subsets, and find the smallest subset
of coins with target sum n

• Solution #2: greedy solution fails

Ø A natural greedy algorithms is to always pick the largest coin
Ø Try the greedy strategy when coins = {1, 3, 4} and n = 6

• Solution #3: DP! (see next slide)

© All Right Reserved

 The Coin Change Problem
DP Solution
• Let 𝑠𝑜𝑙𝑣𝑒(𝑛) be a recursive function that returns the minimal
number of coins for a target sum n
• If coins = {1, 2, 5}, then we can formulate the following:
𝑠𝑜𝑙𝑣𝑒(𝑛) = min ( 1 + 𝑠𝑜𝑙𝑣𝑒(𝑛 – 1) , Try all coins and
1 + 𝑠𝑜𝑙𝑣𝑒(𝑛 – 2), find which one is
the optimal choice
1 + 𝑠𝑜𝑙𝑣𝑒(𝑛 – 5) )

• In general, we can formulate the following:

+∞, 𝑛<0
𝑠𝑜𝑙𝑣𝑒(𝑛) = 0 0, 𝑛=0
𝑚𝑖𝑛! " !#$%& 1 + 𝑠𝑜𝑙𝑣𝑒 𝑛 − 𝑐 , 𝑛>0

© All Right Reserved

The Coin Change Problem
DP Implementation

© All Right Reserved

The Coin Change Problem
Reducing Recursion

• We added this if-statement to

skip recursion for invalid
coins, i.e., coins with values
bigger than the sum n
• In general, always put more
efforts into reducing the
number of recursive calls

© All Right Reserved

The Coin Change Problem
Memorization
We use this map to store
sub-problems solutions

© All Right Reserved

The Coin Change Problem
Printing the Coins
Stores the first choice for
the optimal answer

© All Right Reserved

 The Coin Change Problem
Non-Recursive Implementation is also Possible

Computation table

Exercise: Modify the code

to also print the coins of
the optimal answer

© All Right Reserved

 Notes about DP

• In general, DP approaches are divided into two types:

§ Top-down DP: uses recursion and memorization
§ Bottom-up DP: uses loops and tabulation

• Top-down DP is generally more intuitive and easier to implement

• On the other hand, Bottom-up DP avoids the overhead of

recursion, which can be prohibitive for some problems
§ But also, in general, the bottom-up approach solves more sup-
problems than the top-down approach

• Which one is faster? It depends on the problem

© All Right Reserved

 The Coin Change Problem Version 2
Problem Statement
• Suppose that we are given a set of k coins {c1, c2, ..., ck} and a target
sum of money n, and we are asked to calculate the total number of
ways to produce a sum n using the coins. There are no restrictions on
how many times we can use each coin value.
• Example:
if coins = {1, 3, 4} and n = 5
then there are six ways, as follows:
1+1+1+1+1 = 5
1+1+3 = 5
1+3+1 = 5
3+1+1 = 5
1+4 = 5
4+1 = 5
© All Right Reserved
 The Coin Change Problem Version 2
DP Solution
• Let 𝑐𝑜𝑢𝑛𝑡(𝑛) be a recursive function that returns the number of ways
to produce a sum n using the coins
• If coins = {1, 3, 4}, then we can formulate the following:
𝑐𝑜𝑢𝑛𝑡(𝑛) = 𝑐𝑜𝑢𝑛𝑡(𝑛 – 1) ,
Try all coins and
+ 𝑐𝑜𝑢𝑛𝑡(𝑛 – 3), add their counts
+ 𝑐𝑜𝑢𝑛𝑡(𝑛 – 4) )

• In general, we can formulate the following:

0, 𝑛<0
𝑐𝑜𝑢𝑛𝑡(𝑛) = 01, 𝑛=0
∑! " !#$%& 𝑐𝑜𝑢𝑛𝑡(𝑛 − 𝑐) , 𝑛>0

© All Right Reserved

The Coin Change Problem Version 2
Bottom-Up DP Implementation

Question: What is the O-

complexity?

Exercise: Do the top-down

DP implementation

© All Right Reserved

 Activities

Solve the following problems:

1. Dice Combination (problem link)
2. Minimizing Coins (problem link)
3. Coin Combinations I (problem link)
4. Coin Combinations II (problem link)

© All Right Reserved

 Summary

• Dynamic Programming (DP) is used to solve complex problems by

breaking them into overlapping sub-problems while storing their
results to avoid redundancy in computation

• There are two ways to implement dynamic programming: top-down

and bottom-up

• In general, dynamic programming is regarded among the most

elegant and also challenging problem-solving paradigms

© All Right Reserved