Code More CreateAppearance
动态规划
求解动态规划的核心问题是穷举。
首先，动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要求解动态规划的核心问题是穷举。来优化穷举过程，避免不必要的计算。
而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。
另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」，才能正确地穷举。
以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。在实际的算法问题中，写出状态转移方程是最困难的，思考状态转移方程：
明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。
按上面的套路走，最后的结果就可以套这个框架：
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 求最值(选择1，选择2...)
斐波那契数列
- 暴力递归
- 带备忘录的递归
- 保存每次计算的结果，取值前先找之前的计算结果
- dp数组的迭代
- 用dp数组存储计算的值，循环到目标值停止
- dp数组的状态压缩
- 用状态压缩来缩小 DP table 的大小，只记录必要的数据
int fib(int n) {
if (n < 1) return 0;
if (n == 2 || n == 1)
return 1;
int prev = 1, curr = 1;
for (int i = 3; i <= n; i++) {
int sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
}
凑零钱问题
dp 数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。
class Solution {
public int coinChange(int[] coins, int amount) {
if(amount==0)return 0;
// dp数组记录某金额需要的最少硬币数量
int[] dp = new int[amount+1];
Arrays.fill(dp,amount+1);
dp[0] = 0;
// 遍历所有子状态
for(int i = 1;i<dp.length;i++){
// 对每种状态都进行硬币的遍历，寻求最佳的结果
for(int coin:coins){
// 如果硬币的值比状态值还大的话，无法满足，跳过
if(coin>i)
continue;
dp[i] = Math.min(dp[i],dp[i-coin]+1);
}
}
// 如果最后结果的值还是等于初始值，那么说明无解
return dp[amount] == amount+1 ? -1 : dp[amount];
}
}
PS：为啥
dp数组初始化为amount + 1呢，因为凑成amount金额的硬币数最多只可能等于amount（全用 1 元面值的硬币），所以初始化为amount + 1就相当于初始化为正无穷，便于后续取最小值。为啥不直接初始化为 int 型的最大值Integer.MAX_VALUE呢？因为后面有dp[i - coin] + 1，这就会导致整型溢出。