动态规划

dp动态规划

解决问题

通常用于解决最优化问题,通常做出一组选择来达到最优解.

特点

• 做出每个选择时,通常会生成与原问题形式相同的子问题
• 多于一个选择子集都会生成相同的子问题(子问题重叠)

关键技术

• 对每个相同的子问题保存其解,当其重复出现时避免重复求解
• 通常可将指数时间的算法转换为多项式级别的算法

步骤

1. 刻画一个最优解的结构特征
2. 递归地定义最优解的值
3. 计算最优解的值,通常采用自底向上的方法
4. 利用计算出的信息构造一个最优解

典型问题

算法导论

钢条切割
求两个序列的最长公共子序列
构造最优二叉搜索树