算法剩余部分

在准备面试的过程中发现之前漏掉了一些算法的整理，在本文中慢慢补齐

动态规划

太抽象，还是以零钱问题为例吧。

其实凡是涉及到这种重叠子问题的，都可以用动态规划。

重叠子问题是啥意思？就是大问题拆解成的小问题，可以递归+缓存，比如电影院第几排或者斐波拉契数列，自顶向下，肯定会有部分重叠子问题，如果用缓存，drill down的时候缓存起来。缺点是什么：这样其实还是会去遍历，只能会再走缓存，性能强一些。

有时候，可以递归+贪心，比如零钱，先从最大面额的开始递归，提高性能。

有没有更厉害的解法？就是动态规划。听着挺唬人的，其实就那样。先按照零钱问题走一遍。

初始化状态 -> 确定状态参数 -> 设计决策的思路

初始化是什么，就是amount=0，需要的最小硬币数，dp[0]=0 然后其他每个的初始值都是 dp[i]=Integer.MAX_VALUE(只需要比amount大就行)

然后是状态参数。啥意思？子问题和原问题之间发生变化的变量。状态参数是dp[j]，它记录了达到金额j所需的最少硬币数量。

然后就是设计决策，状态转移方程，描述了如何从已知状态推导出未知状态的过程。要怎么逐步获取到我们要的结果dp[amount]呢？对于每种硬币coin，考虑将其加入到构成总金额的过程中。对于每一个j >= coin，我们检查如果使用了一个面值为coin的硬币，那么剩余的金额变为j - coin。如果dp[j - coin]已经有了一个有效的值（即不是Integer.MAX_VALUE），说明存在一种方式可以凑成j - coin，那么我们就可以通过增加一个coin硬币来考虑凑成j的方案，即更新dp[j] = min(dp[j], dp[j - coin] + 1)。这里dp[j - coin] + 1意味着在已有凑成j - coin最少硬币数基础上再加一个硬币。

我们从最小的金额开始，逐步向上构建，直到求得目标金额amount所需的最少硬币数。每一步的决策都是基于之前的最优解，确保了最终得到的是全局最优解。

对应代码

public class Solution322 {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        // 初始化
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        // 状态方程
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i-coin]+1);
                }
            }
        }
        return dp[amount] == amount+1 ? -1:dp[amount];
    }
}