322. 零钱兑换

题目：

322. 零钱兑换
在这里插入图片描述

题解：动态规划

1. 解释一：

在这里插入图片描述

2. 解释二：

在这里插入图片描述

3. 解释三：

动态规划：尝试分解子问题
- 在研究了好几天，看了大佬们无数的解题思想之后，我终于明白了动态规划的本质，其实理解
  一个算法的思想，有很多时候只差临门一脚，希望我的题解能帮助到大家。
- 我们经常听到「最优子结构」「缩小问题规模」「自顶向下」「自底向上」等跟动态规划
  相关的词汇。
- 接下来就彻底搞懂这种思想，顺带着我自己也重温一遍刚刚搞懂的喜悦。
----------------开始解题，拿实例来说话----------------------
- 假设给出的不同面额的硬币是[1, 2, 5]，目标是 120，问最少需要的硬币个数？
- 我们要分解子问题，分层级找最优子结构，看到这又要晕了哈，憋急~~ 下面马上举例。
- 这里我们使用「自顶向下」思想来考虑这个题目，然后用「自底向上」的方法来解题，
  体验算法的冰火两重天。
- dp[i]: 表示总金额为 i 的时候最优解法的硬币数
- 我们想一下：求总金额 120 有几种方法？下面这个思路关键了 !!!
  一共有 3 种方式，因为我们有 3 种不同面值的硬币。
  1.拿一枚面值为 1 的硬币 + 总金额为 119 的最优解法的硬币数量
    这里我们只需要假设总金额为 119 的最优解法的硬币数有人已经帮我们算好了，
    不需要纠结于此。(虽然一会也是我们自己算，哈哈)
    即：dp[119] + 1
  2.拿一枚面值为 2 的硬币 + 总金额为 118 的最优解法的硬币数
    这里我们只需要假设总金额为 118 的最优解法的硬币数有人已经帮我们算好了
    即：dp[118] + 1
  3.拿一枚面值为 5 的硬币 + 总金额为 115 的最优解法的硬币数
    这里我们只需要假设总金额为 115 的最优解法的硬币数有人已经帮我们算好了
    即：dp[115] + 1
  - 所以，总金额为 120 的最优解法就是上面这三种解法中最优的一种，也就是硬币数最少
    的一种，我们下面试着用代码来表示一下：
  - dp[120] = Math.min(dp[119] + 1, dp[118] + 1, dp[115] + 1);
  - 推导出「状态转移方程」：
    dp[i] = Math.min(dp[i - coin] + 1, dp[i - coin] + 1, ...)
    其中 coin 有多少种可能，我们就需要比较多少次，那么我们到底需要比较多少次呢？
    当然是 coins 数组中有几种不同面值的硬币，就是多少次了~ 遍历 coins 数组，
    分别去对比即可
  - 上面方程中的 dp[119]，dp[118]，dp[115] 我们继续用这种思想去分解，
    这就是动态规划了，把这种思想，思考问题的方式理解了，这一类型的题目
    问题都不会太大。

4. 解释四：

在这里插入图片描述

代码：动态规划

/** * code322 */
public class code322 { 
    public static int coinChange(int[] coins, int amount) { 
        int max = 100000000;    // 一亿
        // dp[i] 保存金额 i 的最小组成数
        int dp[] = new int[amount + 1];
        for (int i = 0; i < dp.length; i++) { 
            dp[i] = max;
        }
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) { 
            for (int j = 0; j < coins.length; j++) { 
                if (coins[j] <= i) { 
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        if (dp[amount] > amount) { 
            return -1;
        } else { 
            return dp[amount];
        }
    }
    public static void main(String[] args) { 
        int coins1[] = {  1, 2, 5 };
        int amount1 = 11;
        int ans1 = coinChange(coins1, amount1);
        System.out.println(ans1);
        int coins2[] = {  2 };
        int amount2 = 3;
        int ans2 = coinChange(coins2, amount2);
        System.out.println(ans2);
    }
}