# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
    for 选择 in 所有可能的选择:
        # 此时的状态已经因为做了选择而改变
        result = 求最值(result, dp(状态1, 状态2, ...))
    return result

# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

    /**
     * 动态规划解题套路框架。
     * 提供我总结的一个思维框架，辅助你思考状态转移方程：
     * 明确 base case -> 明确「状态」 -> 明确「选择」 -> 定义 dp 数组/函数的含义。
     * 
     * 基本思路
     * 1、确定 base case，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。
     * 2、确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount 。
     * 3、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。
     * 4、明确 dp 函数/数组的定义：输入一个目标金额 n ，返回凑出目标金额 n 的最少硬币数量。
     * 按照 dp 函数的定义描述「选择」，得到最终答案 dp(amount) 。
     *
     * 自顶向下的带备忘录的递归解法
     */
    public int coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
        // 备忘录初始化为一个不会被取到的特殊值，代表还未被计算
        Arrays.fill(memo, -666);

        // 题目要求的最终结果是 dp(amount)
        return dp(coins, amount);
    }

    // 备忘录
    int[] memo;

    // 定义：要凑出金额 n，至少要 dp(coins, n) 个硬币
    int dp(int[] coins, int amount) {
        // base case
        if (amount == 0) {
            return 0;
        }
        if (amount < 0) {
            return -1;
        }
        // 查备忘录，防止重复计算
        if (memo[amount] != -666) {
            return memo[amount];
        }

        int res = Integer.MAX_VALUE;
        // 做选择，选择需要硬币最少的那个结果
        for (int coin : coins) {
            // 计算子问题的结果
            int subProblem = dp(coins, amount - coin);
            // 子问题无解则跳过
            if (subProblem == -1) {
                continue;
            }
            // 在子问题中选择最优解，然后加一
            res = Math.min(res, subProblem + 1);
        }
        // 把计算结果存入备忘录
        memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
        return memo[amount];
    }

    /**
     * 动态规划解题套路框架。
     * 提供我总结的一个思维框架，辅助你思考状态转移方程：
     * 明确 base case -> 明确「状态」 -> 明确「选择」 -> 定义 dp 数组/函数的含义。
     * 
     * 基本思路
     * 1、确定 base case，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。
     * 2、确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount 。
     * 3、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。
     * 4、明确 dp 函数/数组的定义：输入一个目标金额 n ，返回凑出目标金额 n 的最少硬币数量。
     * 按照 dp 函数的定义描述「选择」，得到最终答案 dp(amount) 。
     *
     * dp 函数的定义：可以凑成总金额 i 所需的 最少的硬币个数为 dp(i)
     * 状态转移方程：
     * dp[i] = min(dp[i], 1 + dp[i - coin])
     *
     * 自底向上的 dp 数组的迭代解法
     */
    public 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 (int i = 0; i < dp.length; i++) {
            // 内层循环，求所有选择的最小值
            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];
    }