什么是动态规划？
怎样向一个四岁的小孩解释动态规划？下面是来自Quora的高票回答
How should I explain dynamic programming to a 4 year old?
writes down “1+1+1+1+1+1+1+1 =” on a sheet of paper*
“What’s that equal to?”
(counting…) “Eight!”
writes down another “1+” on the left*
“What about that?”
(quickly…) “Nine!”
“How’d you know it was nine so fast?”
“You just added one more”
“So you didn’t need to recount because you remembered there > were eight! Dynamic Programming is just a fancy way to say > ‘remembering stuff to save time later’”
下面的讲解是来自知乎的高票回答：
当你企图使用计算机解决一个问题是，其实就是在思考如何将这个问题表达成状态（用哪些变量存储哪些数据）以及如何在状态中转移（怎样根据一些变量计算出另一些变量）。所以所谓的空间复杂度就是为了支持你的计算所必需存储的状态最多有多少，所谓时间复杂度就是从初始状态到达最终状态中间需要多少步！
每个阶段只有一个状态->递推
每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心
每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。
动态规划: 形式化讲解
动态规划的三兄弟：
- 最优子结构
- 重叠子问题
- 无后效性
最优子结构是指原问题的最优解包含子问题的最优解，例如，求解斐波那契数列fib(n) = fib(n - 1) + fib(n - 2), 第n项斐波那契数必包含第n-1项和第n-2项斐波那契数。就我的经验而言，刻画最优子结构往往是最难的，我常常会因为找错了最优子结构而写错了DP转移方程。像斐波那契数，跳台阶，0-1背包等这种简单的问题，最优子结构很容易刻画，因为当前状态(i,j) 仅依赖于很少的的几个先前的状态，从而状态转移方程是很容易写出来的。然而，常常问题一复杂，其中牵涉的状态较多时，状态转移会变得很复杂，很容易把子问题想错，或者想漏了。在刻画最优子结构时，必须考察完全其最优解需要的所有子问题，做到不重不漏。
还有一点，考虑当前状态(i, j)是从先前的哪些状态转移过来时，是一个决策的过程，所有容许的可能决策构成一个允许决策集，这个集合是由原问题给出的，也是由怎样去设计状态所决定的，并不是自己空想的、臆造的。
重叠子问题是指将原问题分解成许多的子问题后，这些子问题都是相互关联的，有所重叠的，这样使用DP才会加速计算。如果发现问题存在大量的重叠子问题，该问题就很有可能能用DP来解。这点也是DP和分治的显著区别，如果子问题是独立的，直接用分支就能解，也就无所谓DP不DP。例如对于排序问题，将其分解为左右两个子段的排序问题，求解这两个子问题是相互独立的，从而这里并不存在重叠子问题。
四步走
- 划分阶段
- 确定状态
- 寻找最优子结构
- (从特例出发考虑最优子结构)
- 考虑最优子结构的一般情况，注意考虑周全
- 写出状态转移方程和边界情况(平凡/退化情况), 注意边界不要写漏
三步走
- 划分阶段
- 考虑平凡情况，如当数组长度为0时
- 考虑一般情况， 如规模为i的问题已解决，如何基于此求解规模为i+1的问题
1->2->3->4, 1->4->2->3
例题讲解
三大算法思路: 搜索，贪心，dp，分治
fib数列 青蛙跳 变态青蛙跳 挖金矿 花瓶美学 数字三角形 背包九问 最长公共子序列 单源最短路径问题