The basic idea of dynamic programming is to decompose the problem to be solved into several sub-problems, first solve the sub-problems, and save the solutions of these sub-problems. If you need to use the solutions of these sub-problems in the future when solving larger sub-problems, you can directly extract these calculated solutions to avoid repeated operations. The solution to saving subproblems can be filled in using the form method, such as saving in an array.
Use a practical example to reflect the algorithmic idea of dynamic programming - the problem of coin change.
Question description:
Suppose there are several coins and there are unlimited quantities. Please find out the minimum number of coins that can make up a certain number of change. For example, several types of coins are [1, 3, 5], the minimum number of coins with a face value of 2 is 2 (1, 1), the minimum number of coins with a face value of 4 is 2 (1, 3), and the minimum number of coins with a face value of 11 is 3 (5, 5, 1 or 5, 3, 3).
Problem analysis:
Assume that the different sets of coins are array coin[0, ..., n-1]. Then find the minimum number of coins with the face value k, then the count function and coin array coin meet this condition:
count(k) = min(count(k - coin[0]), ..., count(k - coin[n - 1])) + 1;
And the previous formula only holds if 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 met, so here involves the problem of backtracking.
So we can create a matrix matrix[k + 1][coin.length + 1], so that matrix[0][j] is all initialized to 0 values, and save the minimum number of coins with a face value of i in matrix[i][coin.length].
And the specific process is as follows:
* k|coin 1 3 5 min * 0 0 0 0 0 0 * 1 1 0 0 1 * 2 2 0 2 * 3 3 1 0 3, 1 * 4 2 2 0 2, 2 * 5 3 3 1 3, 3, 1 * 6 2 2 2 2 2, 2, 2 * ...
Finally, the specific Java code implementation is as follows:
public static int backTrackingCoin(int[] coins, int k) {//Backtracking method + dynamic programming if (coins == null || coins.length == 0 || k < 1) { return 0; } int[][] matrix = new int[k + 1][coins.length + 1]; for (int i = 1; i <= k; i++) { for (int j = 0; j < coins.length; j++) { int preK = i - coins[j]; if (preK > -1) {//Only when it is not less than 0, preK can exist in the array matrix and backtracking can be performed. matrix[i][j] = matrix[preK][coins.length] + 1;//The face value i is backtracking if (matrix[i][coins.length] == 0 || matrix[i][j] < matrix[i][coins.length]) {//If the current number of coins is the smallest, update the minimum number of coins in the min column matrix[i][coins.length] = matrix[i][j]; } } } return matrix[k][coins.length]; }The code has been tested, and all the test cases given by the question have passed!
Summarize
The above is the entire content of this article about the coin change problem implementation code of Java dynamic programming. I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!