动态规划

动态规划是怎么解决问题的：状态转移方程，最优子结构

思考状态转移方程：

明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case。

动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。

通过备忘录，dp table优化递归树

动态规划的五个注意事项：动态规划不是只有状态转移方程

• dp数组及下标的含义
• 递推公式
• dp数组如何初始化
• 遍历顺序：在背包问题中尤其重要。
• 打印dp数组：dp的debug方式，通过自己明确的dp数组的定义，以及递推公式，来打印dp数组看是否符合推测。

问题们：

01背包：

416. 分割等和子集

474. 一和零

494. 目标和

879. 盈利计划

1049. 最后一块石头的重量 II

1230. 抛掷硬币

完全背包：

1449. 数位成本和为目标值的最大数字

322. 零钱兑换

518. 零钱兑换 II

279. 完全平方数