零钱兑换问题

// 备忘录
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;
}

// 备忘录
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] 枚 https://qimok.cncoin
• base case：dp[0] = 0
• 动态转移方程：dp[i] = Mahttps://qimok.cnth.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];
}

• dp[i] 表示：当目标金额为 i 时的https://qimok.cn组合数
• 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];
}