322. Coin Change

问题

给定一个整数，和几种硬币面值，问最少用几个硬币可以组成这个整数

每个面值可以无限用

无法组成返回-1。

解析

一开始想复杂了。想去借鉴Perfect Square的路子。

用三层循环去做。

for （int i = 0; i <= anount; i++) {
    for (int coin : coins) {
        for (int j = 0; j * coin <= i; j++) {
            dp[i] = Math.min(dp[i], dp[j*coin] + dp[i - j*coin]);
        }
    }
}

其实这种方法应该也行，但是昨晚做的时候脑子转不动了。没想明白。最后提交是错的。今天早上跑了一下case，发现应该需要将每种coin的基础case，即整体的初始化做好才可以利用这个方式。

今天早上从头重新开始想这个问题，还是需要研究下，看这个题目，想要拿到组成amount最少数量的硬币，可以那么其实可能是amount - coin数量的值， 再加1（那个coin本身）。这里也是子问题。

所以我们自底向上去看这个问题。要求组成某个值的最少数量硬币，每次都可以穷举硬币，看是否是子问题加一个硬币可以解决。不断往前走直到达到最终结果。初始化应该要把所有的value除了第一个置为范围（0-10000）以外的值；第一个值置为0，因为组成0数量的硬币为0种，根据题意，没有面值为0的硬币。

状态转移公式那就可以得到dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)。

你如果刚做了一个背包问题，会发现和基础背包问题也很像。

代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, 10001);
        dp[0] = 0;
        
        for (int i = 0; i <= amount; i++) {
            for (int j = n-1; j >= 0; j--) {
                if (i >= coins[j]) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        
        return dp[amount] == 10001 ? -1 : dp[amount];
    }
}

1. Coin Change

Question

Given an integer, and several coin denominations, ask how many coins can be used to form the integer

Each denomination can be used indefinitely

If it cannot be formed, return -1.

Solution

At first I thought it was too complicated. I wanted to take a page from Perfect Square.

Use a three-level loop to do it.

for (int i = 0; i <= anount; i++) {
    for (int coin : coins) {
        for (int j = 0; j * coin <= i; j++) {
            dp[i] = Math.min(dp[i], dp[j*coin] + dp[i - j*coin]);
        }
    }
}

In fact, this method should also work, but last night when doing the brain can not turn. I didn't think it through. The final submission was wrong. This morning I ran a case and found that I should need to make the base case of each coin, that is, the initialization of the whole well before I can take advantage of this way.

This morning to restart the problem from scratch, or need to study the next, look at this topic, want to get composed of am** least number of coins, can then actually may be am - coin number of values, plus 1 (that coin itself). Here is also the subproblem.

So let's look at this problem from the bottom up. Ask for the minimum number of coins that make up a certain value, and each time you can exhaust the coins to see if the subproblem can be solved by adding one coin. Keep going forward until you reach the final result. The initialization should be to set all the values except the first to a range (0-10000); the first value is set to 0, because the number of coins that make up 0 is 0 kinds of coins, according to the question, there is no coin with a face value of 0.

State transfer formula then you get dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1).

You'll find it's also similar to the base backpack problem if you just did a backpack problem.

code

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, 10001);
        dp[0] = 0;
        
        for (int i = 0; i <= amount; i++) {
            for (int j = n-1; j >= 0; j--) {
                if (i >= coins[j]) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        
        return dp[amount] == 10001 ? -1 : dp[amount];
    }
}