长大后想做什么？做回小孩！

0%

LeetCode——零钱兑换

发表于 更新于 分类于 Valine：
本文字数： 413

NO.322 零钱兑换 中等

3vz7RI.png

思路一：深度优先遍历 暴力方法超时！检查所有的组合方式，找出符合要求的组合中硬币数量最少的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int ans = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) {
    if (coins==null||coins.length==0)return -1;
    dfs(coins,amount,0);
    return ans==Integer.MAX_VALUE?-1:ans;
}
//深搜，count记录硬币数量
private void dfs(int[] coins, int amount, int count) {
    //如果小于0，说明当前组合不对，回溯
    if (amount<0){
        return;
    }
    //等于0说明当前组合正确，如果硬币数量更少，则更新结果
    if (amount==0){
        ans=Math.min(ans,count);
        return;
    }
    for (int i = 0; i < coins.length; i++) {
        dfs(coins,amount-coins[i],count+1);
    }
}

时间复杂度：O(amount^n) n是不同面额硬币的种类

思路二：动态规划 dp数组的含义：dp[i]=x 表示至少x个硬币组成i元，即i元的最优解。

dp数组初始化：长度为amount+1，即0元~amount元。dp[0]=0，0元自然是不需要硬币。1~amount初始化为amount+1，因为硬币面额都是整数无论如何amount元也不会需要amount+1个硬币进行组合。

状态转移：无论当前目标金额是多少，都要从coins列表中取出一个面额，然后目标金额就会减少这个面额。如果dp[当前金额-取出面额]有解，则dp[当前金额]就是在其子问题dp[当前金额-取出面额]的基础上加一个硬币。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int coinChange(int[] coins, int amount) {
    int[] dp=new int[amount+1];
    //初始化
    Arrays.fill(dp,amount+1);
    dp[0]=0;
    //填写dp
    for (int i = 1; i <= amount; i++) {
        //金额i的所有子问题
        for (int coin : coins) {
            //不存在这个子问题
            if (i-coin<0)continue;
            //在子问题的基础上加一个硬币，取最小值
            dp[i]=Math.min(dp[i],dp[i-coin]+1);
        }
    }
    //检查amount是否有解
    return dp[amount]==amount+1?-1:dp[amount];
}

时间复杂度：O(amount*n) n是不同面额种类

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github