2024.3.24力扣每日一题——零钱兑换

题目来源

力扣每日一题；题序：322

我的题解

方法一 记忆化搜索

使用深度优先遍历可以得到答案，但是重复计算比较多，因此采用记忆化搜索——在深度优先搜索的过程中记录状态

时间复杂度：O(Sn)。S表示需要匹配的金额，n表示面额数
空间复杂度：O(S)

class Solution {
    int memo[];
    public int coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
		//初始为最小值
		Arrays.fill(memo, Integer.MIN_VALUE);
        memo[0] = 0;
        dfs(coins,amount);
        return memo[amount];
    }
    public int dfs(int[] coins, int amount){
        if (amount < 0) {
			return -1;
		}
		if (memo[amount] != Integer.MIN_VALUE) {
			return memo[amount];
		}
		int res = amount + 1;
		for (int coin : coins) {
			int temp = dfs(coins, amount - coin);
			if (temp == -1) {
				continue;
			}
			res = Math.min(res, temp + 1);
		}
        memo[amount]=res == amount + 1 ? -1 : res;
		return memo[amount];
    }
}
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

方法二 动态规划

记忆化搜索一般都可以直接转为动态规划实现。转移方程：dp[i]=Math.min(dp[i],dp[i-coin]+1)

时间复杂度：O(Sn)
空间复杂度：O(n)

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
		Arrays.fill(dp, amount+1);
		dp[0] = 0;

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

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈