算法

零钱兑换问题

言七墨 · 10月18日 · 2020年 · · 397次已读

一、零钱兑https://qimok.cn换 I

自顶向下、使用备忘录(HashMap)递归解法

// 备忘录
Map<Integer, Integer> memoMap = new HashMap<>();
public int coinChange(int[] coins, int amount) {
    // 查备忘录,避免重复计算
    if (memoMap.containsKey(amount)) {
        return memoMap.get(amount);
    }
    // base case
    if (amount == 0) return 0;
    // 下面的递归入参,假如 amount - coin < 0,则返回 -1
    if (amount < 0) return -1;
    // 最差的情况,就是使用 amount 个面值为 1 的硬币,而 amount + 1 就是个不存在的值,下面要比较最小值,则每次递归都使用 amount + 1 比较求最小值即可
    int res = amount + 1;
    for (int coin : coins) {
        // 子问题(目标金额减去当前 coin)
        int subProblem = coinChange(coins, amount - coin);
        if (subProblem == -1) continue;
        // 求最值,即 res 与 子问题加上一个 coin(与上面`目标金额减去当前 coin`相对应,即自顶向下的思想) 求最值
        res = Math.min(res, subProblem + 1);
    }
    res = res == amount + 1 ? -1 : res;
    memoMap.put(amount, res);
    return res;
}

自顶向下、使用https://qimok.cn备忘录(数组)递归解法

七墨博客
// 备忘录
int[] memo;
public int coinChange(int[] coins, int amount) {
    memo = new int[amount + 1];
    return helper(coins, amount);
}

private int helper(int[] coins, int amount) {
    // 递归终止条件
    if (amount == 0) return 0;
    // 下面的递归入参,假如 amount - coin < 0,则返回 -1
    if (amount < 0) return -1;
    // 查备忘录,避免重复计算
    if (memo[amount] != 0) return memo[amount];
    // 最差的情况,就是使用 amount 个面值为 1 的硬币,而 amount + 1 就是个不存在的值,下面要比较最小值,则每次递归都使用 amount + 1 比较求最小值即可
    int res = amount + 1;
    for (int coin : coins) {
        // 子问题(目标金额减去当前 coin)
        int subProblem = helper(coins, amount - coin);
        if (subProblem == -1) continue;
        // 求最值,即 res 与 子问题加上一个 coin(与上面`目标金额减去当前 coin`相对应,即自顶向下的思想) 求最值
        res = Math.min(res, subProblem + 1);
    }
    memo[amount] = res == amount + 1 ? -1 : res;
    return memo[amount];
}

动态规划(自顶向下)

  • dp[i] 表示:当目标金额为 i 时,至少需要 dp[i] 枚 coin
  • base case:dp[0] = 0
  • 动态转移方程:dp[i] = Math.min七墨博客(dp[i], dp[i – coin] + 1);
public int coinChange(int[] coins, int amount) {
    // 数组大小为 amount + 1,初始值也为 amount + 1
    int[] dp = new int[amount + 1];
    // dp 数组初始值为 amount + 1 的原因:凑成 amount 金额的数最多只可能等于 amount(全用面值为 1 的 coin),所以初始化为 amount + 1 就相当于初始化为正无穷,便于后续取最小值。
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;
    // 外层 for 循环在遍历所有状态的所有取值
    // i 作为状态:表示目标金额
    for (int i = 0; i < dp.length; i++) {
        // 内层 for 循环在求所有选择的最小值
        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];
}

二、零钱兑换 II

动态规划(自顶向下)

  • dp[i] 表示:当目标金额为 i 时的组合数
  • base case:dp[0] = 1
  • 动态转移方程:dp[i] += dp[i – coin]
public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    // base case
    dp[0] = 1;
    // 遍历所有的 coin 面值
    for (int coin : coins) {
        // 对于每个面值,将从金额 0 遍历到 amount,即 dp[0] + dp[1] + dp[2] + ... + dp[amount]
        for (int i = coin; i <= amount; i++) {
            // 对于每个 i,计算组合数:dp[i] += dp[i - coin]
            dp[i] += dp[i - coin];
        } 
    }
    return dp[amount];
}

三、拓展:完全平方数(类似题目)

动态规划(自顶向下)

  • dp[i] 表示:当目标值为 i 时,可以得到最少的平方数的个数
  • base case:dp[i] = 0
  • 动态转移方程:dp[i] += dp[i – coin]
public int numSquares(int n) {
    // 默认初始化值都为 0
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        // 最坏的情况是每次都加 1
        dp[i] = i;
        for (int j = 1; i - j * j >= 0; j++) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        }
    }
    return dp[n];
}
言七墨

0 条回应