class Solution { public int coinChange(int[] coins, int amount) { int []dp = new int[amount+1]; //初始化为amount+1, 便于后面min比较 for(int i=1; i<amount+1; i++) { dp[i] = amount+1; } dp[0] = 0; //外层循环枚举所有可能的面值 for(int i=0; i<amount+1; i++) { //内层循环求出该面值下所有可能选择的最小值 for(int coin : coins) { //过滤掉不可能的情况 if(i<coin) { continue; } dp[i] = Math.min(dp[i], dp[i-coin]+1); } } return (dp[amount]==(amount+1)) ? (-1) : dp[amount]; }
时间: 2023-03-27 20:04:39 浏览: 82
这是一个关于硬币找零的问题,使用动态规划算法来解决。具体实现过程中,先将dp数组初始化为amount+1,然后外层循环枚举所有可能的面值,内层循环求出该面值下所有可能选择的最小值。最后返回dp[amount],如果等于amount+1,则返回-1。
相关问题
把下面的代码转成javaclass Solution(object): def coinChange(self, coins, amount): self.cache = {} def helper(coins, curAmount): if curAmount in self.cache: return self.cache[curAmount] globalMin = amount + 1 if curAmount == 0: return 0 if curAmount < 0: return amount + 1 for coin in coins: curMin = helper(coins, curAmount - coin) if curMin == globalMin: continue globalMin = min(curMin + 1, globalMin) self.cache[curAmount] = globalMin return globalMin result = helper(coins, amount) return -1 if result == amount + 1 else result
这段代码是 Python 代码,将其转化为 Java 代码后,可以得到如下的代码:
```
public class Solution {
private Map<Integer, Integer> cache = new HashMap<>();
public int coinChange(int[] coins, int amount) {
int result = helper(coins, amount);
return result == amount + 1 ? -1 : result;
}
private int helper(int[] coins, int curAmount) {
if (cache.containsKey(curAmount)) {
return cache.get(curAmount);
}
int globalMin = amount + 1;
if (curAmount == 0) {
return 0;
}
if (curAmount < 0) {
return amount + 1;
}
for (int coin : coins) {
int curMin = helper(coins, curAmount - coin);
if (curMin == globalMin) {
continue;
}
globalMin = Math.min(curMin + 1, globalMin);
}
cache.put(curAmount, globalMin);
return globalMin;
}
}
```
这段 Java 代码与原来的 Python 代码功能相同,它采用了递归加缓存的方式来解决硬币兑换问题。具体来说,它将原来的 `cache` 字典替换成了 `cache` 哈希表,使用了 Java 语言自带的 `Map` 类来实现。此外,Java 代码中的列表表示方式也与 Python 代码稍有不同,需要使用数组来代替。最后,Java 代码中的条件语句、循环语句等基本语法结构与 Python 代码也存在一些细微的差异,需要注意语法的转化。
int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; // 数组⼤⼩为 amount + 1,初始值也为 amount + 1 Arrays.fill(dp, amount + 1); // base case dp[0] = 0; // 外层 for 循环在遍历所有状态的所有取值 for (int i = 0; i < dp.length; i++) { // 内层 for 循环在求所有选择的最⼩值 for (int coin : coins) { // ⼦问题⽆解,跳过 if (i - coin < 0) {continue; } dp[i] = Math.min(dp[i], 1 + dp[i - coin]); } } return (dp[amount] == amount + 1) ? -1 : dp[amount]; }
这是一个使用动态规划解决硬币找零问题的代码。该算法的基本思路是:对于任意的金额数,我们都可以通过计算凑出该金额所需的最小硬币数来解决问题。具体步骤如下:
1. 创建一个长度为 amount+1 的数组 dp,初始值为 amount+1,用来存储凑出每个金额所需的最小硬币数。
2. 将 dp[0] 的值设置为 0,表示凑出金额为 0 所需的最小硬币数为 0。
3. 遍历 dp 数组,对于每个 i,遍历硬币数组 coins,如果当前硬币面值 coin 小于等于 i,那么说明可以使用该硬币凑出金额为 i,此时更新 dp[i] 的值为 dp[i-coin]+1 和 dp[i] 本身中的较小值。
4. 最终返回 dp[amount],如果其值等于 amount+1,则说明无法凑出该金额,返回 -1。
该算法的时间复杂度为 O(amount * n),其中 n 是硬币数组的长度。