DP笔记(10)：背包相关问题，零钱兑换
Author：zhoulujun Date：
零钱兑换兑换问题
零钱兑换（322. Coin Change）：给你一组不同面额的硬币和一个总金额，问最少需要多少张硬币可以凑成这个总金额。
零钱兑换 II（518. Coin Change 2）：给你一组不同面额的硬币和一个总金额，问有多少种方法可以凑成这个总金额。
322 可以使用动态规划或回溯算法求解，而 518 通常使用动态规划求解。 本篇都用动态规划来解题
零钱兑换
给定不同面额的硬币 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
当我一眼看完题目，我判断出这道题应该要用动态规划的思维来做，主要有两个原因：
有可选择的东西（硬币）
求到达一个目标数（amount）的最小硬币数（也就是最优解）
解决动态规划问题，就是一个求最优解的问题，同时也是一个求最优子解的问题，在零钱问题中，求到amount的最小硬币数，就是求到amount前子问题的最小硬币数。
前子问题是什么？
我们先举个例子，输入: coins = [1, 2, 5], amount = 11 输出: 3
目标数是11，那目标数的子问题是什么？
没错，就是 amount - coins，在这道题中就是10, 9, 6
那题就转换成了去求到达目标数10，到达目标数9，到达目标数6的最小硬币数，
继续这样缩小范围，直到最基本的问题，也就是amount == 1的时候。
我们采用自下而上的方式进行思考。仍定义 F(i) 为组成金额 iii 所需最少的硬币数量，假设在计算 F(i) 之前，我们已经计算出 F(0)−F(i−1) 的答案。 则 F(i) 对应的转移方程应为
前面我们说了，动态规划问题要找出状态和选择，
状态是什么？
状态就是到达这个目标数的最小硬币数！
选择是什么？选择就是这个硬币我选还是不选？
依据是什么？依据是能不能让我硬币数达到最小，
比如到达目标数8，是让 5 + 1 + 1 + 1呢？ 还是5 + 2 + 1呢？
当然就是后者，这就是选择。
dp数组记录的是什么？是状态。
那可以转换成我们的状态转移方程了，
// dp[i] 初始化为最大值 dp[i] = MAX_VALUE dp[i] = min(dp[i - coins] + 1, dp[i]) // i 代表当前目标数 // coins代表硬币数额 // +1，表示加上一个硬币数
状态转移方程的问题解决了，这道题也就解决了一半了
转载本站文章《DP笔记(10)：背包相关问题，零钱兑换》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9124.html