This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 518 on LeetCode. Change for II. Difficulty is Medium.

Give coins of different denominations and a total amount.

Write a function to calculate the number of coin combinations that add up to the total.

Suppose there are an infinite number of coins of each denomination.

Example 1:

Input: Amount =5, Coins = [1, 2, 5] Output: 4 Explanation: There are four ways to make a total amount: 5=5 5=2+2+1 5=2+1+1 5=1+1+1+1+1 +1Copy the code

Example 2:

Input: Amount = 3, Coins = [2]Copy the code

Example 3:

Input: Amount = 10, Coins = [10] Output: 1Copy the code

Note:

You can assume:

  • 0 <= amount <= 5000
  • 1 <= coin value <= 5000
  • There are no more than 500 types of coins
  • The result conforms to a 32 – bit signed integer

Complete knapsack (Simple solution)

In the previous question [322. Change], we found “the minimum number of items needed to obtain a particular value”.

In this case, we are looking for “the number of solutions that achieve a particular value”.

Different things, but the nature of the problem has not changed, it is also a “combinatorial optimization” problem.

You can understand what a combinatorial problem is like this:

There is no need to satisfy a specific relationship between the selected items, only the selected items to achieve “global optimum” or “specific state”.

Coins also act as our items, and each coin can be selected “unlimited times”, which naturally comes to mind as “full backpack”.

At this point, the “full backpack” state definition can be moved over to “fine tune” :

define
f [ i ] [ j ] f[i][j] To consider before
i i The sum of the items is
j j The number of programs.

To facilitate initialization, we generally let f[0][x]f[0][x]f[0][x] stand for the case where no item is considered.

So we have obvious initialization conditions: f [0] [0] = 1 f [0] [0] = 1 f [0] [0] = 1, the rest f [0] [x] = 0 f [0] [x] [0] = 0 f (x) = 0.

Represents when there are no coins, the number of schemes with a sum of 0 is 1; There is no scheme that adds up to the other sum.

When “state definition” and “basic initialization” are in place, we consider without loss of generality how f[I][j]f[I][j]f[I][j] should be transferred.

For coin III we have two decision options:

  • Do not use the coin:


f [ i ] [ j ] = f [ i – 1 ] [ j ] f[i][j] = f[i – 1][j]

  • Use the coin: Since each coin can be selected multiple times (capacity permitting), the number of options should be the sum of options for selecting “any” of the coins:


f [ i ] [ j ] = ∑ k = 1 ⌊ j / v a l ⌋ f [ i – 1 ] [ j – k ∗ v a l ] . v a l = n u m s [ i – 1 ] f[i][j] = \sum_{k = 1}^{\left \lfloor {j / val} \right \rfloor}f[i – 1][j – k * val], val = nums[i – 1]

Code:

class Solution {
    public int change(int cnt, int[] cs) {
        int n = cs.length;
        int[][] f = new int[n + 1][cnt + 1];
        f[0] [0] = 1;
        for (int i = 1; i <= n; i++) {
            int val = cs[i - 1];
            for (int j = 0; j <= cnt; j++) {
                f[i][j] = f[i - 1][j];
                for (int k = 1; k * val <= j; k++) {
                    f[i][j] += f[i - 1][j - k * val]; }}}returnf[n][cnt]; }}Copy the code
  • Time complexity: A total of N ∗ CNTN * CNTN ∗ CNT states need to be transferred, and CNTCNTCNT will be traversed at most for each state transfer. The overall complexity is O(n∗ CNT2)O(n * CNT ^2)O(n∗ CNt2).
  • Space complexity: O(N ∗ CNT)O(n * CNT)O(n∗ CNT).

Full knapsack (one-dimensional optimization)

Obviously, the complexity of two-dimensional complete knapsack solution is a little high.

The data range of NNN is 10210^2102, and the data range of CNTCNTCNT is 10310^3103. The total calculation amount is more than 10810^8108, which is on the edge of timeout (the actual test can pass).

We need to “dimensionally reduce” it, and we can use the mathematical analysis we started with, or the substitution optimization we talked about last time.

Because mathematical analysis is very time-consuming, we use more substitution optimization. Both are also “generalizable”.

Since the latter is more commonly used, let’s review how to perform an commutation one-dimensional optimization:

  1. On the basis of two-dimensional solution, directly cancel “item dimension”
  2. Ensure that the “capacity dimensions” are traversed in “from small to large” order (for “full knapsack”)
  3. Will shape such as f [I – 1] [j – k ∗ val]] [I – 1 f [j – k * val] f [I – 1] [j – k ∗ val] formula for f [j – val] [j – val] f f [j – val]. Also resolve “array out of bounds” issue (change item dimension traversal to start from valvalval)

Code:

class Solution {
    public int change(int cnt, int[] cs) {
        int n = cs.length;
        int[] f = new int[cnt + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            int val = cs[i - 1];
            for (intj = val; j <= cnt; j++) { f[j] += f[j - val]; }}returnf[cnt]; }}Copy the code
  • Time complexity: A total of N ∗ CNTN * CNTN ∗ CNT states need to be transferred, and the overall complexity is O(n∗ CNT)O(N * CNT)O(n∗ CNT).
  • Space complexity: O(CNT)O(CNT)O(CNT)

conclusion

[322. Change for Change] is essentially the same as “518. Change for CHANGE II” in this article.

So the two problems are divided into two [exercises], mainly to strengthen your proficiency in “one-dimensional optimization”.

Coming up with a “two-dimensional plain version” and then doing a “mathematical analysis” is too slow for a competition or a written test.

We should be able to write a “one-dimensional optimization” version as soon as we get started, but at the same time have two-dimensional recursive logic in mind

The last

This is the No.518 of our “Brush through LeetCode” series. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.