322. 零钱兑换

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

            //这里我们要求最小组合数，因此这里可以填充最大值
            Arrays.fill(dp, Integer.MAX_VALUE);

            //0元的组合必然啥都么有
            dp[0] = 0;

            for (int i = 1; i <= amount; i++) {
                //遍历每种可能
                for (int coin : coins) {
                    //1. i - coin >= 0 意思当前硬币要小于等于我们要凑的钱数,另外要凑的子金额要大于0;
                    //2. dp[i - coin] != Integer.MAX_VALUE 意思我们剩下的钱也是要能凑齐的才行；
                    //   不是所有的dp都有意义，有可能这个组合就是不存在，因此这里也可以理解为只有除掉不可拆分的硬币之外剩余的钱必须能被凑齐才有意义做为比较值；
                    if (i - coin >= 0 && dp[i - coin] != Integer.MAX_VALUE) {
                        dp[i] = Math.min(dp[i - coin] + 1, dp[i]);
                    }
                }
            }

            return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
        }


    }