322. 零钱兑换

一 题目

二 思路:

动态规划既找子问题,由子问题递推大问题.

拆分coins =[1, 2, 5]，amount=11,那么面值为11的最小可能和为以下可能的最小值:

• 面值为1的硬币最小可能组合数（1），加面值为（11-1）=10的最小可能组合数量
• 面值为2的硬币最小可能组合数，加面值为9的最小可能组合数量
• 面值为5的硬币最小可能组合数，加面值为6的最小可能组合数量

我们 设dp[amount]为金额为amount的最小可能组合
这里dp[11]=min(1+dp[11-coins[0],1+coins[11-coins[1],1+coins[11-coins[2])

即dp[amount] = min(dp[amount], 1 + dp[amount - coins[i]]) for i in [0, len - 1] if coins[i] <= amount

同时我们要知道和注意:

• 某些子dp就是有可能不存在,这种情况我们不需要进行比较,因为它不是我们大的金额的子问题

三代码:

 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];
        }


    }