322. 零钱兑换 - Java 动态规划 背包DP

原题地址：https://leetcode.cn/problems/coin-change/

题解

这是一道完全背包DP问题的变种：给定一个容器和数个可取无限次的不同体积的物品，求能放下的最多物品数

而这道题则是给定一个容器和数个可取无限次的不同体积的物品，求刚好能放满背包的最少物品数

设dp[i]为用coins凑出金额i的最小硬币数，用j遍历coins，我们可以认为金额i是由金额i-coins[j]加上一个硬币coins[j]得到的，那么有

考虑一种情况，若能够组成dp[i]的dp[i-coins[j]]均不存在，说明无法组成金额i，则金额i也应当不存在，所以应当用一个available数组维护dp[i]的存在性

• 若dp[i]遍历到的dp[i-coins[j]]均不存在(!available)，min不会被更新，则设dp[i]也不存在(available=false)
• 遍历结束时若available[amount]也为false，则说明不存在能够组成amount的组合

边界情况：

当dp[0]时，不需要任何硬币即可组成0，所以dp[0]=0且available[0]=true，此外，当dp[i]刚好满足i∈coins时，dp[i]恰好等于dp[0]+1即1

时间复杂度：O(N^2)

空间复杂度：O(N)

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp=new int[amount+1];
        boolean[] available=new boolean[amount+1];
        dp[0]=0;
        available[0]=true;

        int min;
        boolean flag;
        for(int i=0;i<=amount;i++){
            min=Integer.MAX_VALUE;
            for(int j=0;j<coins.length;j++){
                if(i-coins[j]>=0&&available[i-coins[j]]){
                    min=Math.min(min,dp[i-coins[j]]+1);
                }
            }
            if(min!=Integer.MAX_VALUE){
                dp[i]=min;
                available[i]=true;
            }
        }

        if(available[amount])
            return dp[amount];
        else
            return -1;
    }
}