Using dynamic programming algorithm to explain the coin change problem

Original link

The coin change problem is recognized as a typical application of dynamic programming algorithm, and its solution includes the computer idea of dynamic programming. Wikipedia defines dynamic programming as follows:

"It is a mathematical optimization method and a computer programming method... It refers to the simplified process of decomposing a complex problem into many simple subproblems."

In other words, dynamic programming is a programming method that simplifies the problem into many smaller problems. For example, if you directly ask how much 3 * 89 equals, you may not be able to answer as fast as the result of asking 2 * 2. But if you already know 3 * 88 = 264, you can infer 3 * 89 = 264 + 3 = 267 in an instant. This is a simple example of dynamic programming, from which we can find a clue of how dynamic programming algorithm can efficiently solve complex problems.

With the above example, let's look at the coin change problem. There are many variants of the coin change problem, and only one of them is listed below. There are a number of coins with different denominations (such as 1 cent, 5 cents and 10 cents). There is no limit to the number. Calculate the number N to make up the amount with these coins, and how many different combinations exist.

Problem simple version

Let's start with a simple example.
Example 1: suppose there are three denominations of coins: 1 cent, 5 cents and 10 cents, and the total amount is N=8 cents, how many combinations can there be?

Input: N=8
      Coins:  1, 5, 10
 Output: 2

Process explanation:
    Combination 1:
        1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8 branch
    Combination 2:
        1 + 1 + 1 + 5 = 8 branch

 

All you have to do is come up with a combination of all amounts equal to 8 points. Eight 1 points equals 8 points, and three 1 points plus one 5 points equals 8 points. Therefore, there are two ways to use 1 point, 5 points and 10 points to form 8 points.

 

A little more difficult.
Example 2: suppose there are three denominations of coins: 1 cent, 5 cents and 10 cents, and the total amount is N=10 cents, how many combinations can there be?

Input: N=19
      Coins:  1, 5, 10
 Output: 4

Process explanation:
    Combination 1:
        1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 10 branch
    Combination 2:
        1 + 1 + 1 + 1 + 1 + 5 = 10 branch
    Combination 3:
        5 + 5 = 10 branch
    Combination 4:
        10 = 10 branch

 

Through the above two examples, it is easy to understand the coin change problem itself and find the answer with smaller N.

But how to find the answer when the value of N is very large? Of course, write code to solve it. How to write the program to calculate how many coin combinations there are when the N value is large? This requires a dynamic programming algorithm. The essence of dynamic programming algorithm is to divide each part of the problem into smaller parts. Just like the process of solving arithmetic problems at the beginning of this paper, if you know that 4 * 35 = 140 but don't know how much 4 * 36 equals, you can directly add 4 to the result of 4 * 35 to get 4 * 36 = 144.

Increase difficulty

The program calculates the number of coin combinations that make up the N amount. The process is similar. Let's take a look at an example first:

N = 12
 Array subscript:[0, 1, 2]
Coin amount:[1, 5, 10]

There are three denominations of coins: 1 cent, 5 cents and 10 cents. The value of N is 12 In other words, we need to find out how many combinations reach 12 points.

 

The result with small N value is easy to calculate, so when calculating N=12, considering the dynamic process, we need to clarify how to add the result with small N value before, so as to avoid repeated calculation of the N value of the known result.
For coins, we need to traverse all coins. If the denomination of coins is greater than the N value, it cannot be used to make up the N value.

One of the solutions of dynamic programming

One of the solutions to the coin change problem is to calculate the combination mode of using coins to form the face value from the face value zero to the face value N.
Namely:

Number of combination methods (hereinafter referred to as ways):

[0, 0, 0, ..., The first N individual] From the above, here N=12

In such an array with a length of N+1 (starting from N=0), the subscript of the element represents the total amount of different combination methods, and the value of the element itself represents the number of combination methods that make up the amount. If the denomination of a coin is greater than the value of the element subscript, the coin cannot be used to make up the amount corresponding to the subscript. For ease of understanding, please refer to the following examples.

Values are inherited from the example above:

N = 12
 Coin array(coins)Subscript:[0, 1, 2]
Coin amount:[1, 5, 10]

Combination method quantity array(ways)Subscript of:
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Combination method quantity array(ways,Predefined status): 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0,  0]

 

Before starting the iteration, we need to define the initial state of the ways array and set the value of the element at the subscript 0 to 1, because there is only one case where we can make up for 0 cents: 0 coins.

Then, we can traverse all coins and compare the face value of coins with the elements of the ways array to determine how many times each coin can be used to make up the amount corresponding to the subscript.

For example, first set ways[0]=1, and then compare the first coin, 1 minute

N = 12
 Coin array(coins)Subscript:[0, 1, 2]
Coin amount:[1, 5, 10]

Combination method quantity array(ways)Subscript of:
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Combination method quantity array(ways,Predefined status): 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0,  0]

compare coins[0]and ways Each element in the array, if coins[0]The value of is less than or equal to ways The subscript of the array element, then ways[j]Set the value of to ways[j-coins[0]]+ways[j]. In this way, each part is broken down into smaller parts, and this process will continue below. Compared coins[0]and ways After all the elements in the array, ways The value of the array will be updated to:


Combination method quantity array(ways)Subscript of:
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Combination method quantity array(ways,And coins[0]After comparison): 
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  1,  1,  1]

 

Continue to compare the second coin, which has a face value of 5 cents.

N = 12
 Coin array(coins)Subscript:[0, 1, 2]
Coin amount:[1, 5, 10]

Combination method quantity array(ways)Subscript of:
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Combination method quantity array(ways,And coins[0]After comparison): 
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  1,  1,  1]

compare coins[1]and ways Each element in the array, if coins[1]The value of is less than or equal to ways The subscript of the array element, then ways[j]Set the value of to ways[j-coins[1]]+ways[j]. In this way, each part is broken down into smaller parts, and this process will continue below. Compared coins[1]and ways After all the elements in the array, ways The value of the array will be updated to:


Combination method quantity array(ways)Subscript of:
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Combination method quantity array(ways,And coins[1]After comparison): 
    [1, 1, 1, 1, 1, 2, 2, 2, 2, 2,  3,  3,  3]

This process is to calculate the second to second n How many times are coins used to form the amount of each subscript value. Why compare all the coins? It is to dynamically update the results of the previous comparison and reduce repeated calculations (compared with the number of combination methods calculated separately for each amount). For example, at this time ways The element value corresponding to subscript 10 is 3. How did it come from? In the calculation,`j-coins[1]`It's 10-5,That is 5, which is the missing part of the amount of 10 in addition to the current coin denomination of 5. And now ways The element value of subscript 5 is 2, that is, there are two ways to make up for 5 at this time. Therefore, the two methods of making up 5 plus the current method of making up 10 (1 before calculation) is the number of updated combination methods of all making up 10 (i.e. 3)

 

Then compare the third coin, which has a face value of 10 cents.

N = 12
 Coin array(coins)Subscript:[0, 1, 2]
Coin amount:[1, 5, 10]

Combination method quantity array(ways)Subscript of:
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Combination method quantity array(ways,And coins[1]After comparison): 
    [1, 1, 1, 1, 1, 2, 2, 2, 2, 2,  3,  3,  3]

compare coins[2]and ways Each element in the array, if coins[2]The value of (10) is less than or equal to ways The subscript of the array element, then ways[j]Set the value of to ways[j-coins[2]]+ways[j]. In this way, each part is broken down into smaller parts, and this process will continue below. Compared coins[2]and ways After all the elements in the array, ways The value of the array will be updated to:


Combination method quantity array(ways)Subscript of:
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Combination method quantity array(ways,And coins[2]After comparison): 
    [1, 1, 1, 1, 1, 2, 2, 2, 2, 2,  4,  4,  4]

knowable N=12 The answer is ways[12],I.e. 4

 

code implementation

The original text has the implementation of Java, Python and C# code, and only the python version is excerpted

def get_num_of_ways(N, coins):
    ways = [0] * (N + 1)
    
    ways[0] = 1
    
    for c in coins:
        for i in range(N+1):
            if c <= i:
                ways[i] += ways[i-c]
    
    return ways[-1]

 

Operation results:

In [3]: get_num_of_ways(10, [1, 5, 10])                                                             
Out[3]: 4

In [4]: get_num_of_ways(20, [1, 5, 10])                                                             
Out[4]: 9

In [5]: get_num_of_ways(100, [1, 5, 10])                                                            
Out[5]: 121

In [6]: get_num_of_ways(1000, [1, 5, 10])                                                           
Out[6]: 10201

reflection

Another article on dynamic programming( ref )It is mentioned that dynamic programming has two solutions: top-down and bottom-up. The solution in the above should belong to bottom-up, starting from the most basic state and gradually inferring the required results.

Reference: steps of listing state transition equations in dynamic programming
  1. Determine the base case, the most basic state that cannot be split, and the solution of the problem at this time
  2. Determine the state, that is, the variables that will change in the original problem and subproblem. Since the number of coins is unlimited and the denomination is preset, only the target amount will keep approaching base case, so the only state is the target amount N
  3. Determine the choice, that is, the behavior that causes the state to change. Why did the target amount change? Because you are choosing a coin, not choosing a coin is equivalent to reducing the target amount to be raised, so the face value of the coin is the choice
  4. Clarify the definition of dp function (in top-down solution) / array (in bottom-up solution). In the above, the definition of array coins is to make up the amount of subscript I. there are coin [i] combinations. You can also change the self-defined dp function. dp(n) requires at least a few coins to make up the amount n, and at least a few coins to calculate the amount n

The base case, the state of the state transition equation, the selection behavior and the definition of dp function / array will change according to the required problems.

Posted by VenusJ on Sat, 07 May 2022 01:05:05 +0300