动态规划四步骤

确定状态

• 研究最优策略的最后一步
• 化为子问题

转移方程

• 根据子问题定义直接得到

初始条件和边界情况

• 细心，考虑周全

计算顺序

• 利用之前的计算结果

常见动态规划类型：

• 坐标型 20%
• 序列型 20%
• 划分型 20%
• 区间型 15%
• 背包型 10%
• 最长序列型 5%
• 博弈型 5%
• 综合型 5%