Java Dynamic programming coin change problem implementation code

The basic idea of dynamic programming is to decompose the problem to be solved into several sub-problems, solve the sub-problems first, and save the solutions of these sub-problems. If the solutions of these sub-problems need to be used in solving larger sub-problems in the future, the solutions that have been calculated can be directly taken out without repeated operations. The solution to the subproblem can be saved by filling in a table, for example, in an array.

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

Problem description:

Let's say I have a bunch of COINS, and I have an infinite number of COINS. Find the smallest number of COINS used to make up a certain number of COINS. For example, some COINS are [1, 3, 5], the minimum number of COINS in denomination 2 is 2(1, 1), the minimum number of COINS in denomination 4 is 2(1, 3), and the minimum number of COINS in denomination 11 is 3(5, 5, 1 or 5, 3).

Problem analysis:

Suppose the different sets of COINS are array coin[0,..., ES13en-1]. Then, find the minimum number of COINS of face value k (k), then the count function and the coin array coin satisfy the following 1 condition:

count(k) = min(count(k - coin[0]), ..., count(k - coin[n - 1])) + 1;
And when eligible k-ES24en [i] > = 0 & & k - coin[i] < In the case of k, the previous formula is true.
Because k - coin[i] < For k's sake, then count(k) must satisfy count(i)(i) < - [0, ES45en-1]) known, so here again 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 zero value, and save the minimum number of COINS in matrix[i][coin.length] with a face value of i.

And the specific process is as follows:

* k|coin 1  3  5  min
  * 0    0  0  0  0
  * 1    1  0  0  1
  * 2    2  0  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
  * ...

Finally, the specific Java code is implemented as follows:

public static int backTrackingCoin(int[] coins, int k) {// backtracking + 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 if it's not less than 0 when , preK To exist in an array matrix In the ,  So you can go back .
          matrix[i][j] = matrix[preK][coins.length] + 1;// Face value i Backtracking 
          if (matrix[i][coins.length] == 0 || matrix[i][j] < matrix[i][coins.length]) {// If the current number of COINS is the lowest ,  update min Minimum number of COINS listed 
            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 title have passed!

conclusion

That's the end of this article on Java dynamic programming coin change problem implementation code, I hope to help you. Those who are interested can continue to see other related topics on this site. If there is any deficiency, please let me know. Thank you for your support!