动规（DP 即 Dynamic Programming）说白了就是一个解决问题的思路——记忆化的，分阶段的，动态化的递推（从直接有结果的基准问题递推到最终问题）。
拿最简单的斐波那契问题举例子，一个大的问题f(n)可以被拆解为小一点的问题f(n-1)和f(n-2)，……直到然后拆到最小的问题f(1)和f(2)。你可以从f(n)从大往小了算，也可以先从f(1), f(2), f(3)……从小往大了算。再比如leetcode的有个正则表达式匹配的问题，你可以把问题看做是一个大的字符串的匹配pattern，拆解为字符串的一部分匹配pattern的一部分的问题；也可以反过来先匹配一小部分，再不断让可以匹配的范围变大。
很多人把从大往小算的形式称作递归（Recursion），反过来从小往大了算称为DP。但实际上只要满足大规模问题可以拆解为小规模问题，这个思路本身就是DP的，无非是顺序不一样罢了。
动态规划就是指知道了一组小规模问题的答案后，就可以用一个方案（状态转移方程）组装成大一点规模问题的答案的做法而已。为啥叫“动态”呢，因为状态转移会和几个条件相关，而不是一开始就可以无脑写死（无脑写死的一般就是贪婪）。
术语上，从大往小算被称为”自顶向下“，而从小往大算被称为”自底向上“。尽管自顶向下和自底向上等价，但自顶向下算一个很容易发生的问题就是重复计算，比如你为了算f(5)，普通的递归方式要重复计算很多很多次f(3), f(2)……。这些计算都是浪费的，实际表现比自底向上差的多（但再强调下，二者的思路没本质差别，仅仅是计算浪费不浪费的问题）。
但你可以加cache，每次递归的函数的参数都可以组装成一个cache的key。这样每次递归时，可以先检查一下cache是不是有，有了就不用算了，直接返回。这种带cache的递归DP一般被称为“记忆化搜索“。记忆化搜索与自底向上的DP计算方式在算法复杂度上理论上是一样的。但cache一般会用map，其实际的复杂度要比直接用数组的自顶向上要大，二者的O(1)是不一样的。此外记忆化搜索还会引入函数调用的开销，所以一般记忆化搜索比等价的自底向上要慢那么一丢丢。
此外自底向上的计算方式还可以优化存储，比如斐波那契计算时，计算f(n)只需要f(n-1), f(n-2)，所以用两个变量就行，无须把所有的结果都记录下来。用go写可以是这样：
//代码效果参考：http://www.zidongmutanji.com/zsjx/15861.html
func fib(n int) int {
f0, f1 := 0, 1
for n > 1 {
f1, f0 = f0 + f1, f1
n--
}
return f1
}
但用记忆化搜索的方式，你是没法在计算得到f(4)后，把f(1)结果占用内存给方便的清理掉的。
DP最难的不在于自底向上还是自顶向下，而在于怎么拆问题。某些问题，如果之前没做过，你是很难想得到“这个问题还能这么拆”。不信？可以去看看LeetCode有一道“戳气球”的题目。我自己第一次看时虽然能猜到它是用DP，但打死都想不出来怎么拆，直到看了题解。因此大家想不出来DP，不是因为不知道DP的代码框架怎么做，而是拆解问题的思路实在太古怪，太反常识。这就需要刷题去多多适应。
But，这些反常识的方法也是人想出来的。此时也是去了解那些聪明人的脑洞的好机会：）。你也许会惊讶于人思维方式的差异的巨大。
在现实工程中，有些问题即便是可以DP，但因为拆解方案对于大部分人来说太难想；或者即使想出来，应用面太窄，需求小小的一个变化就会让整套方案不灵了。因此很多时候，如果复杂度的要求不那么严苛，还是用暴力要好一些。因此DP更常见于面试题里，证明候选人“知道像计算机专业从业者那样思考”。但这并不是说DP不重要，在计算机科学里，这个思路非常非常重要，只不过工程上不光要考虑算法复杂度，还要考虑可维护性问题而已。如果场景恰当，当然还是要用。比方说，“计算基金最大回撤”就可以用DP，实际上就是LeetCode里“买卖股票最佳时机”解题方案的镜像——就是一个算回撤，一个算正向收益的区别。
回到DP本身，如果觉得自顶向下的思路很舒服，那就总是先用递归实现自顶向下DP。通过后加上Cache用记忆化搜索的方式写代码。再改写成等价的自顶向上的做法。反复做几次看看思路上能不能贯通。但同时，有时也会省得写自底向上很舒服，反过来就别扭。
当然，虽然二者等价，可能会遇到很难自底向上写的问题。此时一般是很难找到一个很简单的从小到大的规律，这就不如用递归+cache。cache的规则就很简单，算过了就cache，没算过就没cache，递归调用中参数出现的规律不需要操心。
最后，递归能够在DP这个思路里支持实现自顶向下，但也不一定就用在DP里。递归适合的场景要更加广泛。比如dfs/bfs这样的搜索场景就可以用递归做。递归还可以用来做模拟，比如A对B做一件事、B又要对C和D做一件事，D又要对A和B做一件事……。用递归来实现很直观。
动态规划指的是题型，即解题思路；而递归指的是解题方法，即实现细节。
动态规划类题型一般有两种实现方式：
bottom-up 即 table-fill
top-down 即递归（recursion）
下面是这两种方式的详细举例。
方法一：bottom-up（table-fill）
//代码效果参考：http://www.zidongmutanji.com/bxxx/242816.html
function fib(n) {
const arr = [0, 1, 1];
for(let i=3; i<=n; i++) {
arr[i] = arr[i-2] + arr[i-1];
}
return arr[n];
}
时间复杂度：O(n)
空间复杂度：O(n)
这种实现方法的好处在于用空间换时间。时间优化了成了 O(n)，但空间也变成了 O(n)。所以一般一维的 DP 大概会用变量来写。
function fib(n) {
let result = 1;
let first = 1;
let last = 1;
for(let i = 3; i <= n; i++) {
first = last;
last = result;
result = first + last;
}
return result;
}
时间复杂度：O(n)
空间复杂度：O(1)
这样一来空间复杂度瞬间降低了一个级别，变为常数级别 O(1)。“利润”非常可观。二维及以上的 DP 则会用滚动数组（rolling array）来优化。
方法二：top-down（recursion）
function fib(n){
if(n === 1 || n === 2){
return 1;
}else{
return fib(n-2) + fib(n-1);
}
}
这种实现方法的优势在于对于每一步看得非常明白，大家能够轻而易举地了解什么是斐波那契数列，对于理解这个结构非常有帮助。但不好的地方在于时间复杂度非常低，低到令人发指、实际应用中不可接受的地步。
Upper bound time complexity: T(n) = O(2^{n})
Tight upper bound time complexity: T(n) = O(1.6180^{n})
具体推算比较枯燥，可以看这里。
时间复杂度： O(1.6180^{n})
空间复杂度：O(1)
//代码效果参考：http://www.zidongmutanji.com/bxxx/294358.html
一种常见的优化手段就是上记忆化缓存 （Memoization）。
function fib(n, memo) {
if(n === 1 || n === 2){
return 1;
}else if(n in memo){
return memo[n];
}else{
memo[n] = fib(n-2, memo) + fib(n-1, memo);
}
return memo[n];
}
console.log(fib(8, {}));
时间复杂度：O(n)
空间复杂度：O(n)
这里由于有了 memo 不用重复运算，基本上只会跑 n 次，所以时间复杂度为 O(n)，空间复杂度为 O(n)。
所以一般的动态规划问题考察中，大家会直接上最优解即 bottom-up 的 table-fill，并且用变量或者滚动数组来优化空间。但值得注意的是最优解并不意味着是最容易理解的实现方式。一般 recurision + memo（业界也叫 DFS + memo）被称为是万金油式的 DP，没有它解不了的题目。而且时间复杂度和空间复杂度都有很好的平衡。
动态规划其实就是把一个复杂的最优解问题分解成一系列较为简单的最优解问题，再将较为简单的最优解问题一步步分解，直到能够一眼看出为止。
动态规划看起来跟递归很像，不过推理逻辑正好是反过来的。递归的逻辑是：“要求得 d[m][n]，先要求得 d[m-1][n-1]……”，动态规划的逻辑是：“先求得 d[m-1][n-1]，再求 d[m][n]……”这是它们的主要区别。
动态规划和记忆化递归一般都是可以相互转化的。
动态规划的dp表就相当于递归中的缓存。
动态规划中的状态转移方程式就相当于递归调用。
通俗一点动态规划就是从下往上（从前向后）阶梯型求解数值。
总的来说动态规划从前向后，递归从后向前，两者策略不同，并且一般动态规划效率高于递归。
不过都要考虑初始状态，上下层数据之间的联系。
