都说这种类型的题是最难的，我也有点惧怕，不过还是要迎难而上。

动态规划问题的一般形式就是求最值，求最值的核心就是穷举，暴力穷举会导致效率低下哎，所以我们需要一个备忘录来优化穷举过程。

而且，动态规划问题一定具备最优子结构，这样才能通过子问题的最值得到原问题的最值

动态规划三要素是重叠子问题（备忘录优化），最优子结构，状态转移方程，最难的一步就是构建出正确的状态转移方程。

动态规划采用自底向上的推理方法，从规模最小的一直推到规模最大的，所以动态规划一般都脱离了递归，采用循环迭代完成计算。

有了这些关于动态规划的了解后，我们来实战一下

凑零钱问题

题目描述：给定不同面额的硬币 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=11时的最少硬币数，假设有数值为1的硬币，其实就是在求amount=10的最少硬币数+1。由于硬币的数量是没有限制的，子问题之间没有相互制约，所以是相互独立的。

我们既然知道该题是动态规划的题了，那么就得认真思考一下它的状态转移方程了。

状态转移方程三部曲

先确定状态

状态即变量，在该题中唯一的状态是目标金额amount

确定dp函数定义

函数dp(n)表示，当前的目标金额n，至少需要dp(n)个硬币凑出该金额

确定选择并择优

对于每个状态，可以做出什么选择改变当前状态。在该题中，无论当前目标金额是多少，选择就是从coins中选一个硬币，然后将目标金额减去选择的硬币值。

好的，现在我们可以得到状态转移方程了

消除重叠子问题

我们使用自底向上的dp table来消除重叠子问题，dp数组的定义与dp函数的定义类似

解题思路

初始化一个长度为amount+1，每个元素初始值为amount+1的dp数组，因为组成amount的最大硬币数为amount(即全都是1的硬币数组成)，初始化为amount+1相当于正无穷，便于后续取最小值

将第0位元素赋值为1，便于后续最小值比对

遍历dp数组，每次相当于计算目标金额为i的最小硬币数

每次遍历都要从coins中选择硬币做为dp[i-coin]（即最优子结构）进行最小值比对

在选择硬币前还要判断子结构是否存在，即i<coin是无效的

代码

var coinChange = function (coins, amount) {
    let dp = Array(amount + 1).fill(amount+1)
    dp[0]=0
    for (let i = 0; i < dp.length; i++) {
        for (let coin of coins) {
            if (i < coin) {
                continue
            }
            dp[i] = Math.min(dp[i - coin]+1, dp[i])
        }
    }
    return dp[amount] == amount+1 ? -1 : dp[amount]
};