当前位置：首页 > article >正文

Leetcode面试经典150题-322.零钱兑换

article 2024/9/30 21:55:23

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

这个题很容易就写成二维的动态规划了，使用一维动态规划需要理清思路，其他的就不多说了，上代码，看不懂的请留言或者私信，收到第一时间解答

class Solution {
    /**本题是零钱兑换系列问题，思路是动态规划，边解题边解释思路吧 */
    public int coinChange(int[] coins, int amount) {
        /**如果只有一种货币，能除尽就直接返回，除不尽返回-1 */
        if(coins.length == 1) {
            return amount % coins[0] == 0? amount / coins[0] : -1;
        }
        /**如果不止一个，使用动态规划进行解题，先定义动态规划数组dp, dp[i]的含义是i这个amount最少由多少个硬币凑成
        我们从小金额到大金额进行循环，比如我们的硬币分别是1,2,5，dp[1]=1 dp[2]=1 dp[3]=2
        dp[4]=Math.min(dp[4-1]+1, dp[4-2]+1)=2
        dp[5]=Math.min(dp[5-1]+1, dp[5-2]+1, dp[5-5]+1)括号里的三个分别表示凑够了4再加个1元，凑够了3再加一张2元，凑够了0再加一张5元
        ...dp[11]= Math.min(dp[11-1]+1, dp[11-2]+1,dp[11-5]+1)*/
        int[] dp = new int[amount + 1];
        /**先都设置为最大值 */
        Arrays.fill(dp, Integer.MAX_VALUE);
        /**0这个金额0个硬币就能凑出来，所以dp[0]=0 */
        dp[0] = 0;
        /**给硬币数组排个序 */
        Arrays.sort(coins);
        /**从1到amount进行遍历 */
        for(int curAmount = 1; curAmount <= amount ; curAmount++) {
            for(int i = 0; i < coins.length; i++) {
                /**如果小于0了，我们dp数组就越界了，而且负数不可能由任何树组成就算它存在也应该是最大值 */
                if(curAmount - coins[i] < 0) {
                    break;
                }
                dp[curAmount] = Math.min(dp[curAmount], dp[curAmount-coins[i]] == Integer.MAX_VALUE? Integer.MAX_VALUE : dp[curAmount-coins[i]] + 1);
            }
        }
        return dp[amount] == Integer.MAX_VALUE? -1 : dp[amount];
    }
}

时间复杂度肯定是最低了，表现一般般，凑活这看吧