leet code 322. 零钱兑换

322. 零钱兑换

题目描述

给你一个整数数组 coins ，表示不同面额的硬币；

以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。

如果没有任何一种硬币组合能组成总金额，返回 -1 。

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

示例 1：

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

示例 2：

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

示例 3：

输入：coins = [1], amount = 0 输出：0

提示：

题目解析

暴力递归

• 硬币数量无限，可以无限选择
• 由此可以画出递归树如下——以示例1为例

• 之所以称为暴力递归，是因为存在相当多的 重复计算

show code

class Solution {

    private int ans = Integer.MAX_VALUE;

    public int coinChange(int[] coins, int amount) {
        return dfs(coins, amount);
    }

    private int dfs(int[] coins, int amount) {
        if(amount == 0) {
            return 0;
        }
        if(amount < 0) {
            return -1;
        }
        for(int coin : coins) {
            ans = Math.min(ans, 1 + dfs(coins, amount - coin));
        }
        return ans == Integer.MAX_VALUE?-1:ans;
    }

}

• 经过测试超时
• 超时原因：大量重复计算，时间复杂度达到了

记忆优化搜索

class Solution {

    private int[] memo;

    public int coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
        // 初始化一个特殊值.
        Arrays.fill(memo, -100);
        return dfs(coins, amount);
    }

    private int dfs(int[] coins, int amount) {
        if(amount == 0) {
            return 0;
        }
        if(amount < 0) {
            return -1;
        }
        // 记忆优化搜索.
        if(memo[amount] != -100) {
            return memo[amount];
        }
        int ans = Integer.MAX_VALUE;
        for(int coin : coins) {
            int c = dfs(coins, amount - coin);
            if(c == -1) {
                continue;
            }
            ans = Math.min(ans, 1 + c);
        }
        return memo[amount] = (ans == Integer.MAX_VALUE)?-1:ans;
    }

}

一比一翻译成迭代

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        // 初始化.
        Arrays.fill(dp, amount + 1);
        // base case.
        dp[0] = 0;
        // 外层for循环遍历所有状态的所有取值.
        for(int i = 0;i <= amount;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. 首先base case dp[0] = 0表示当金额为0的时候所需要的硬币最少为 0 枚
2. 根据dp[0]去计算dp[1]，当 i = 1：i - coin表示是否存在解，不存则跳过
3. 依次类推