知乎一篇高赞动态规划
《labuladong的算法小抄-动态规划章节》

动态规划应用比较多的情况是求最值。核心问题是穷举。
首先动态规划三要素：
1.记忆数组/重叠子问题。
2.最优子结构。
3.状态转移方程。

对于记忆数组，我想说的是，最传统的递归暴力解法会有很多的重复计算，最终的结果以来历史计算的结果，那动态规划就可以减少重复计算。

最优子结构：首先要符合最优子结构，子问题必须相互独立。例如我们接下来的每个例题都会分析是否能用动态规划来做，在凑零钱问题中，硬币数量没有限制，任何子问题都没有限制，互相独立。分享一个例子：你参加考试，你的原问题是考出最高的总成绩，那么你的子问题就是把各科成绩都考到最高分，各科最高分那你的每道题都是最高分。。。。最终结果就是满分。那这个问题符合最优子结构，每门课程考到最高分，这些子问题互相独立、互不干扰。但如果有个条件，你的语文数学成绩相互制约，数学成绩高，就会语文低，那就会子问题不独立，各科无法同时达到最优解。

做题步骤：
1.定义数组（很重要），dp[i]含义。
2.找出数组元素关系式，这里我分享自己的思路就是，一般都是第n个结果是什么，那第n个结果之前的结果是什么，这往往是我做题中的破题之处。例如：斐波那契数列，dp[n] = dp[n-1] + dp[n-2];矩阵从左上角到右下角，求最大值，那到右下角前会经过哪里？；凑零钱问题，在得到最少的硬币个数dp[n]之前，得到dp[n]= min(dp[n-coin]+1 ,dp[n]);coin表示硬币面值，n表示需要凑的金额。
3.base case最简单案例，初始化。

1 凑零钱问题

给你一个整数数组 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
示例 4：
输入：coins = [1], amount = 1
输出：1
示例 5：
输入：coins = [1], amount = 2
输出：2

class Solution {
    public int coinChange(int[] coins, int amount) {
        //定义数组，amount == i 的时候最少的硬币数量
        int[] dp = new int[amount+1];
        //初始化
        for(int i = 0; i < amount+1; i++){
            dp[i] = amount+1;
            //最差的结果就是无数个1相加，那amount+1相当于无穷大。
            //代表-1，表示无解
        }
        dp[0] = 0;
        //开始循环
        for(int i = 1; i < amount+1; i++){
            for(int j = 0; j < coins.length; j++){
                if(i - coins[j] < 0) continue;
                dp[i] = Math.min(dp[i], 1 + dp[i-coins[j]]);
            }
        }
        return (dp[amount] == amount+1)?-1: dp[amount];
    }
}