# Dynamic programming: which recurrence relation do we use?

• MHB
• mathmari
In summary, we discussed the use of a greedy algorithm to give change using the minimum number of coins, and analyzed its time complexity in the worst case. We also explored the possibility of outputting an array with the numbers of each coin in addition to the minimum number of coins. Then, we were asked to generalize the problem and create a dynamic programming algorithm to find the optimal solution, but we were unsure about the recurrence relation and how to use dynamic programming in this scenario. We also looked at a suggested code for the dynamic programming solution and questioned the variables and methods used in it.
mathmari
Gold Member
MHB
Hey! :unsure:

At the cash register of a store we want to give change of worth $V$ cents of euro. Create and analyze a greedy algorithm that gives the change using the minimum number of coins.
Assume that the available coins are the euro subdivisions, i.e. $\{1, 2, 5, 10, 20, 50\}$ and that we have an unlimited number of coins for each subdivision.

For this question I have done the following pseudocode:

Code:
Algorithm min_number_coins (C, V)
Input: array C={1,2,5,10,20,50} in ascending order and given value V
Output: array A with minum number of coins
A <- ∅
for i <- 5 downto 0 do
while V >= C[i] do
A <- A U C[i]
V <- V - C[i]
if V = 0 then
return A

Is that correct? At the for loop is it correct to take $i$ from $5$ or do I have to set a new variable n = length(C) ? :unsure:

For the complexity: In the worst case we need $V$ coins for the change, if we have only the subdivision $1$. So the complexity of the for-loop and so also of the algorithm is $O(V)$, right? :unsure: Now I am asked the following:

Generalizing the above problem, we have the set of different coins $\{c_0, c_1,\ldots , c_n\}$ with $c_0 <c_1 <\ldots <c_n$ from which we want to give the change of value $V$ using the minimum number of coins. We consider that $c_0 = 1$.
Create and analyze a dynamic programming algorithm that finds an optimal solution to the problem, commenting on both time and space complexity of the algorithm.

Could you explain to me the idea how we use the dynamic programming here? I mean the recurrence relation that we have to use. I haven't really undersood that. :unsure:

For the dynamic programming I have found the below code:

So we calculate for eacj $j$ between $1$ and $V$ the set with the minimum number of coins to get the value $j$, right? :unsure:

mathmari said:
Input: array C={1,2,5,10,20,50} in ascending order and given value V
Output: array A with minum number of coins
A <- ∅
for i <- 5 downto 0 do
...

Is that correct? At the for loop is it correct to take $i$ from $5$ or do I have to set a new variable n = length(C) ?

Hey mathmari!

The use of 5 would be fine if C were a local constant. But it's not. Instead it's an input and the input specification does not say that it is of size 5.
So it is indeed better to use length(C) instead of 5. There is no need to introduce a new variable n for it though.
Do note that length(C) is 6 and not 5.

For the complexity: In the worst case we need $V$ coins for the change, if we have only the subdivision $1$. So the complexity of the for-loop and so also of the algorithm is $O(V)$, right?

Well, we have C as input, and it is not given that it only has the subdivision $1$.
And with the given C and algorithm, we will only have a maximum of 4 cents.
However, given the largest coin c, it will take $\lfloor V / c\rfloor$ iterations to find the number of coins $c$. Beyond that we have a fixed worst case number of iterations to divide the remainder. So the complexity is indeed $O(V)$.

Btw, we can also output an array with the numbers of each coin, couldn't we?
Then we could use $A[ i ] \leftarrow A[ i ] + 1$.

Now I am asked the following:

Generalizing the above problem, we have the set of different coins $\{c_0, c_1,\ldots , c_n\}$ with $c_0 <c_1 <\ldots <c_n$ from which we want to give the change of value $V$ using the minimum number of coins. We consider that $c_0 = 1$.
Create and analyze a dynamic programming algorithm that finds an optimal solution to the problem, commenting on both time and space complexity of the algorithm.

Could you explain to me the idea how we use the dynamic programming here? I mean the recurrence relation that we have to use. I haven't really understood that.

I guess we could make the algorithm recursive.
That is, we can find how many times the largest coin fits and make a recursive call to divide the remainder with the set of coins that excludes that largest coin.

mathmari said:
For the dynamic programming I have found the below code:

View attachment 10840So we calculate for eacj $j$ between $1$ and $V$ the set with the minimum number of coins to get the value $j$, right?
What are $d$, $k$, $n$, $C$, and $S$?

And how is this a dynamic programming solution?
Doesn't dynamic programming imply that the problem is broken into smaller sub problems in a recursive fashion?

## 1. What is dynamic programming and how is it different from other programming paradigms?

Dynamic programming is a method for solving complex problems by breaking them down into smaller, simpler subproblems. It differs from other programming paradigms because it focuses on solving a problem by solving smaller versions of the same problem, rather than trying to solve the entire problem at once.

## 2. What is a recurrence relation and why is it important in dynamic programming?

A recurrence relation is a mathematical equation that defines a sequence of values based on previous values in the sequence. It is important in dynamic programming because it allows us to break down a complex problem into smaller subproblems and use the solutions to those subproblems to solve the larger problem.

## 3. How do we determine which recurrence relation to use in dynamic programming?

This depends on the specific problem at hand. Generally, we want to find a recurrence relation that represents the optimal substructure of the problem, meaning that the optimal solution can be built from optimal solutions to smaller subproblems. We also want to make sure that the subproblems overlap, so that we can use the solutions to smaller subproblems to find the solution to the larger problem.

## 4. Can we use dynamic programming to solve any type of problem?

No, dynamic programming is not suitable for all types of problems. It is most effective for problems that exhibit optimal substructure and overlapping subproblems. If these conditions are not met, other problem-solving methods may be more appropriate.

## 5. How do we know when to stop using dynamic programming and when to use another approach?

If the problem at hand does not have optimal substructure or overlapping subproblems, then dynamic programming may not be the best approach. Additionally, some problems may have a more efficient solution using a different method. It is important to analyze the problem and consider all possible approaches before deciding on the best one.

Replies
2
Views
1K
Replies
15
Views
3K
Replies
1
Views
2K
Replies
13
Views
2K
Replies
8
Views
2K
Replies
29
Views
2K
Replies
5
Views
3K
Replies
6
Views
2K
Replies
18
Views
6K
Replies
3
Views
17K