Dynamic Programming

动态规划问题的种类更杂，一般来讲也更 tricky 一些。因为这类问题建立在对问题的状态空间和子问题结构有清晰的认识，并且能正确定义和缓存子问题结果上。即使最后的代码看起来可能只是几个循环，但是从复杂程度上大多数要高于暴力搜索和二叉树。

什么情况下使用动态规划，满足下面三个条件之一：

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

什么情况下不使用动态规划：

• 求出所有 具体的方案而非方案个数 • http://www.lintcode.com/problem/palindrome-partitioning/
• 输入数据是一个 集合 而不是 序列 • http://www.lintcode.com/problem/longest-consecutive-sequence/
• 暴力算法的复杂度已经是多项式级别
  • 动态规划擅长与优化指数级别复杂度(2^n, n!)到多项式级别复杂度(n^2,n^3)
  • 不擅长优化n^3到n^2

动规四要素

• 状态 State 灵感, 创造力, 存储小规模问题的结果

• 方程 Function 状态之间的联系, 怎么通过小的状态, 来算大的状态

• 初始化 Initialization 最极限的小状态是什么, 起点

• 答案 Answer 最大的那个状态是什么, 终点

递归三要素

• 定义(状态)
  • 接受什么参数
  • 做了什么事
  • 返回什么值
• 拆解(方程)
  • 如何将参数变小
• 出口(初始化)
  • 什么时候可以直接 return

常见动态规划：

• 坐标型 10%
• 接龙型 20%
• 单序列型 5%
• 匹配型 15%（双序列）
• 划分型 20%
• 背包型 20%
• 区间型 10%

见到题基本的判断，用 DP 做的题大多返回 boolean / int ，求 Max /Min ，而且不能打乱原输入顺序。

动态规划有两个重要定义，一个叫 "optimal substructure"，另一个叫 "overlap subproblem".

各种排序 / Tree 类问题中，都会用到 divide & conquer 的思想，去把问题分成若干个 "disjoint" subproblems，然后递归解决。+

"Disjoint" subproblem 在 Tree 类问题上体现的最为明显，左子树是左子树的问题，右子树是右子树的问题。因此 Tree 类问题上，更多的是解决“disjoint subproblem 的整合” 还有 “非连续 subproblem 的处理”。

而动态规划的中心思想是，面对 search tree 里都是 "overlap subproblem"，如何根据问题结构制定缓存策略，避免重叠问题重复计算。