Implementation code of coin change problem in Java Dynamic Programming

The basic idea of dynamic programming is to decompose the problem to be solved into several subproblems, solve the subproblems first, and save the solutions of these subproblems. If the solutions of these subproblems need to be used in solving larger subproblems in the future, these calculated solutions can be taken out directly without repeated operation. The solution of the sub problem can be saved by filling in a form, such as saving in an array.

A practical example is used to reflect the algorithm idea of dynamic programming - coin change problem.

Problem Description:

Suppose there are several coins and the number is infinite. Please find the minimum number of coins that can form a certain number of change. For example, several coins are [1,3,5], the minimum number of coins with face value 2 is 2 (1,1), the minimum number of coins with face value 4 is 2 (1,3), and the minimum number of coins with face value 11 is 3 (5,5,1 or 5,3)

Problem analysis:

Suppose different groups of coins are array coin [0,..., n-1] Then find the minimum number of coins count (k) with face value K, and the count function and coin array coin meet the following condition:

count(k) = min(count(k - coin[0]),count(k - coin[n - 1])) + 1; And the above formula is valid only when the condition K - Coin [i] > = 0 & & K - Coin [i] < K is met Because K - Coin [i] < K, when calculating count (k), count (I) (I < - [0, k-1]) must be known. Therefore, backtracking is involved here

Therefore, we can create a matrix [K + 1] [coin. Length + 1], initialize all matrix [0] [J] to 0, and save the minimum number of coins with face value I in matrix [i] [coin. Length]

The specific process is as follows:

Finally, the specific java code implementation is as follows:

The code has been tested and all the test cases given in the title have passed!

summary

The above is the whole content of the coin change implementation code of Java Dynamic Programming in this paper. I hope it will be helpful to you. Interested friends can continue to refer to other related topics on this site. If there are deficiencies, please leave a message to point out. Thank you for your support!