322. 零钱兑换(基础)

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

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

示例 2:

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

说明:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change

思路：

dp

用dp[i]表示目标金额为i时需要的硬币数量

这一题是动态规划中的最基础，最经典的，一定要掌握

注意：

一定要将初始条件写上，之前调不出来就是没写dp[0]=0，这样就很难受

然后可以将dp数组初始化为amount+1，相当于无穷大

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int coinChange(int[] coins, int amount) {
        //dp[i]表示目标金额为i时的零钱个数
        int[] dp = new int[amount+1];
        //这一步用来为啥 dp 数组初始化为 amount + 1 呢，因为凑成 amount 金额的硬币数最多只可能等于 amount（全用 1 元面值的硬币），所以初始化为 amount + 1 就相当于初始化为正无穷，便于后续取最小值
        Arrays.fill(dp,amount+1);
        dp[0]=0;//base
        //第一层用来循环所有状态的所有取值
        for(int i=1;i<=amount;i++){
            //第二层用来循环零钱的种类
            for(int coin :coins){
                if(i>=coin)//如果剩余的不够，就跳过
                    dp[i] = Math.min(dp[i],dp[i-coin]+1);//不选，选
            }
        }
        return (dp[amount]==amount+1)?-1:dp[amount];//目标钱币状态没改变即达不到要求

    }
}

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//超时，纯递归算法
class Solution {
    public int coinChange(int[] coins, int amount) {
        return coinHelper(coins,amount);

    }
    //递归方法,n为需要找的金额
    int coinHelper(int[] coins,int amount){
        int res = amount+1;
        if(amount==0){
            return 0;
        }
        if(amount<0){
            return -1;
        }
        for(int coin : coins){
            if(amount-coin<0){
                continue;
            }
            //System.out.println("1--"+coin);
            int count = coinHelper(coins,amount-coin);
            //System.out.println("2--"+count);
            //如果没有解
            if(count==-1){
                continue;
            }
            res = Math.min(res,count+1);
            //System.out.println("3--"+res);
        }
        return res==amount+1?-1:res;
        //return res;
    }
}

代码3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//加备忘
class Solution {
    int[] memo;
    public int coinChange(int[] coins, int amount) {
        memo = new int[amount+1];
        return coinHelper(coins,amount);
    }
    //递归方法,n为需要找的金额
    int coinHelper(int[] coins,int amount){
        int res = amount+1;
        if(amount==0){
            return 0;
        }
        if(amount<0){
            return -1;
        }
        if(memo[amount] != 0){
            return memo[amount];
        }
        for(int coin : coins){
            if(amount-coin<0){
                continue;
            }
            //System.out.println("1--"+coin);
            int count = coinHelper(coins,amount-coin);
            //System.out.println("2--"+count);
            //如果没有解
            if(count==-1){
                continue;
            }
            res = Math.min(res,count+1);
            //System.out.println("3--"+res);
        }
        res =res==amount+1?-1:res;
        memo[amount]=res;
        return res;
        //return res;
    }
}