Dynamic Programming

概述

内容主要来源于九章算法.

极有可能使用 DP 的条件:

• 求最大最小值
• 判断是否可行
• 统计方案个数

不适用 DP 的条件:

• 求具体方案, 而非个数
• 暴力解已经是多项式复杂度了

DP 四要素

• 状态
• 状态转换方程
• 初始化
• 结果

常见 DP 类型:

• 坐标型
• 序列型
• 双序列型
• 划分型
• 背包
• 区间

实现方式

自底向上

循环: 从小到大递推, 通过表格记录递推过程

自顶向下

从大到小搜索, 记忆化搜索.
    - 画搜索树
    - 大的问题的解来自小的问题 (DFS)