上一篇中已经对回溯思想和递归结构进行了简单的分析：
https://www.jianshu.com/p/193a800e7d5f

本篇重点在分治和动规以及递归和动态规划的不同应用。

分治策略（Divide and Conquer）

将原问题分解为若干个规模较小但类似于原问题的子问题（Divide），递归的求解这些子问题（Conquer），然后再合并这些子问题的解来建立原问题的解。

动态规划（Dynamic Programming）

动态规划其实和分治策略是类似的，也是将一个原问题分解为若干个规模较小的子问题，递归的求解这些子问题，然后合并子问题的解得到原问题的解。
区别在于这些子问题会有重叠，一个子问题在求解后，可能会再次求解，于是我们想到将这些子问题的解存储起来，当下次再次求解这个子问题时，直接拿过来就是。

其实就是说，动态规划所解决的问题是分治策略所解决问题的一个子集，只是这个子集更适合用动态规划来解决从而得到更小的运行时间。
即用动态规划能解决的问题分治策略肯定能解决，只是运行时间长了。因此，分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。

将「动态规划」的概念关键点抽离出来描述就是这样的：
1.动态规划法试图只解决每个子问题一次
2.一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。

动态规划公式

【最优子结构】—— 多种情况的结果及选择方法
【状态转移公式】 —— 一般是多维数组，每个维度表示一个状态；状态值作为子函数的param传递。
【边界】——子函数在碰到边界时，return结果给上层。
子函数中会填充当前层的状态数组。因此，每一层递归跳出后，能自下而上的直接用数组中更小状态的结果。

动态规划的操作步骤（接地气版）

动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤：

1. 定义历史记录的数组含义，每个维度表示什么。
2. 找出数组元素之间的关系式（就是传说中的最优子结构）
3. 找出初始值，要严谨。一般一位数组初始化首尾；二位数组初始化第一行和第一列。

动态规划的优化思路

基本 80% 的二维矩阵 dp 都可以优化成 一维矩阵的 dp
核心就是要画图，看他们的值依赖

Tips

1. 90% 的字符串问题都可以用动态规划解决，并且90%是采用二维数组。
2. 80% 的动态规划题都可以画图，其中 80% 的题都可以通过画图一下子知道怎么优化

从递归到动态规划

上一篇说了递归理论上都能变成栈或动规。

1、用一次次入栈出栈的过程(没有任何好处) —— 每一次调用子函数，都使用到了当前层的某个结果作为param。
如：二叉树遍历，会把当前节点的子节点作为参数传给子函数。
2、优化成从小向大求解即动态规划(空间换时间) —— 当前层使用到了子函数return的值。
如：爬台阶，会用到两个子函数的返回值相加。

leetcode相关练习