零钱兑换00

题目链接

零钱兑换

题目描述

注意点

• 如果没有任何一种硬币组合能组成总金额，返回 -1
• 可以认为每种硬币的数量是无限的

解答思路

• 动态规划从总金额1开始推出目标金额所需的最少硬币个数，任意某个金额所需的最少硬币个数可以由当前金额减去每种面额的硬币，通过前置金额所需的最少硬币个数加1就是当前金额所需的最少硬币个数

代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            int minNum = -1;
            for (int coin : coins) {
                if (i -  coin < 0 || dp[i - coin] < 0) {
                    continue;
                }
                minNum = minNum < 0 ? dp[i - coin] : Math.min(minNum, dp[i - coin]);
            }
            dp[i] = minNum < 0 ? minNum : (minNum + 1);
        }
        return dp[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

关键点

• 动态规划的思想