动态规划总结

动态规划算法

动态规划算法，就是挖掘问题的条件，找到问题中各个状态的联系，通过列出状态转移方程，实现各个状态的计算。

动态规划解题思路

动态规划解题的核心是找到状态转移方程，如何表示状态，如何求解状态就是DP问题的难点。下面给出动态规划解题的一般思路：

集合的强调

这个思路特地强调了集合这个概念，与传统的DP思路略有不同，一些问题求解时可能不需要强调集合这个概念，就可以顺利得到状态转移方程，但有一些较为复杂的问题如果从集合的角度来思考，就更容易进行状态的划分与计算。

状态划分的技巧

经验上讲，我们通常对达成状态的最后一步进行划分。

DP的难点

上面，我们基于经验总结了DP问题的一般解决思路，但实际上都不会如此顺利，可能存在以下问题：

• 无法找到合适的状态表示方法
• 当前状态表示的方法无法进行有效的状态划分，无法计算

所以DP问题非常灵活，不存在模板，只能不断积累经验，碰到以上问题可以尝试着迁移其它问题的状态表示和状态划分方法。

动态规划的类型

动态规划总结起来共以下几种类型：

• 线性DP
• 区间DP
• 计数类DP
• 数位统计DP
• 状态压缩DP
• 树形DP

每类问题的处理存在一些共性，但笼统的总结其特点没有意义，Blog中对这些类型的题目均有记录，时常翻看才能提高对DP的掌握。

动态规划的实现

动态规划算法有两种实现：

• 循环实现各种状态的计算
• 记忆化搜索，递归的实现状态的计算

前者实现的速度一般略快于后者，但有时采用后者可以更加清晰简洁的实现算法，应该结合具体问题，选择合适的实现方式。