322. [✔][M]零钱兑换

给你一个整数数组 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 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

---

题解：

动态规划解题套路框架

// @lc code=start
function coinChange(coins: number[], amount: number): number {

    // 自底向上
    // dp[i]表示总金额为i的话最少需要几个硬币
    let dp = new Array(amount + 1).fill(amount + 1);

    // base条件
    dp[0] = 0;

    for (let i = 0; i < dp.length; i++) {
        for (const coin of coins) {
            if (i < coin) {//相当于需要的金额比这个硬币还小
                continue;
            }
            dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
        }
    }

    return (dp[amount] === amount + 1) ? -1 : dp[amount];

    // // 自顶向下
    // let memo = new Array(amount + 1).fill(-999);

    // const dp = (coins: number[], total: number): number => {

    //     // base条件
    //     if (total === 0) {
    //         return 0
    //     }
    //     if (total < 0) {
    //         return -1;
    //     }

    //     // 备忘录
    //     if (memo[total] !== -999) {
    //         return memo[total];
    //     }

    //     let res = Number.MAX_SAFE_INTEGER;

    //     // 做选择，计算子问题
    //     for (const coin of coins) {
    //         let subProblem = dp(coins, total - coin);
    //         if (subProblem === -1) {
    //             continue;
    //         }
    //         res = Math.min(res, subProblem + 1);
    //     }

    //     // 存入备忘录
    //     memo[total] = (res === Number.MAX_SAFE_INTEGER) ? -1 : res

    //     return memo[total];
    // }

    // return dp(coins, amount);
};
// @lc code=end