思想

求最值：穷举。空间换时间。
在穷举中存在重叠子问题（比如斐波那契数列，如果用递归的话可能需要反复计算同一个fib(n)），所以使用备忘录优化穷举过程。如图所示，时间复杂度O(2^n) ->O(n)
如果用自底向上的思想，则更加清晰。避免了重复运算。
存在最优子结构，状态转移方程：

状态压缩：压缩dp table的大小，比如斐波那契数列其实只用保存前两个数字就行了，而不用保存整个dp数组。

框架

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

例题

322. 零钱兑换

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 自底向上解法
        // dp[i] = 剩余i块钱的时候的最少组合方法
        int[] dp = new int[amount + 1];
        // 将所有的dp元素赋值为正无穷(最坏情况是amount，所以+1相当于正无穷))
        Arrays.fill(dp, amount + 1);
        // base case 0元不需要凑
        dp[0] = 0;
        for (int i = 0; i < dp.length; ++i) {
            for (int coin : coins) {
                if (i - coin < 0) continue;
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }
}