递归和动态规划

递归和动态编程(Dynamic Programming, DP)是算法类问题中的难点所在。算法的核心在于找到状态转移方程，即如何通过子问题解决原问题。在“The Rules”部分，我们先介绍递规和DP的普适特性；再通过“模式识别”，从题目的关键字出发，判断什么样的题目适合用递归和DP，并且总结算法模版

解题策略

用动态编程(自底向上)解决收敛结构问题

具有强收敛性/Aggregate属性的问题(承前所述，是指关于特解，或最值，或总和，或数量的问题)，都可以用整数坐标映射所有节点，且当前节点的解只依赖于前驱节点(无论是顺序还是倒序)。那么，这类问题往往可以用DP解决。解决的关键是建立子问题的解之间的递推关系：
f(n) = G[f(n-1), f(n-2), … , f(1)] 或
f(i, j) = G[f(i-1, j-1), f(i, j -1), f(i-1,j)]
其中G[ ]表示子问题到原问题的映射关系，例如对于斐波那契数列，有递推式：
f(n) = G[f(n-1), f(n-2)] = f(n-1) + f(n-2)

解决这类问题的时候，可以把上述递推关系写在手边，这样做非常有利于理清算法实现的思路。实际实现算法时，往往以问题的一端为循环开端，另一端为循环终止条件，将当前节点的解(或往往是，以当前节点为末节点的问题的解，抑或是以当前两个坐标为输入的问题的解)用DP table(即数组)记录下来(如果当前节点只由之前紧接的若干个节点决定，那么用若干个变量也够了)，数组的下标即为子问题的输入变量，也就是递推关系中的函数参数，只是把f(i,j)表示成array[i][j]而已。

如果问题除了要计算动归终点的数值以外，还需要记录具体的到达路径，则可记录每个节点的前驱节点(prev[n])或前驱路径(vector<vector<int>> prev)，然后用终点出发通过backtracking处理成path。这时候记录的前驱们都是经过了DP的剪枝，每一条路径都是符合条件的正确路径。

注意，如果出现类似于“所有解”，“所有路径”等关键词，则用自上而下方法更为直接。之后我们也会给出例子。

最长子序列类型的问题

对于“最长子序列”问题(即有限空间内，满足一定条件的最长顺序子序列)，本身具有很强的聚合性，可以以如下方式解答：用DP Table来记录以当前节点为末节点的序列的解(至少固定问题的一端，因此不是以“当前节点或之前节点”为末节点)的解，并根据递推关系，由问题空间的起点到达问题空间的终点。

用Memorization (Top-Down)解决收敛结构问题

Memorization是自顶向下形式的动态编程，并且受到的制约更少，自然也可以用来解决前述的问题(但空间上可能效率不及自底向上形式的DP)。

Memorization的核心在于，在原有递归框架下，存储子问题的计算结果，在重复计算子问题时返回已经计算的值。

值得注意的是，这里所谓的“重复计算子问题”，在自顶向下结构下必须与前驱节点无关，因为子问题并不知道原问题是如何到达当前节点的。举例来说，求二叉树从根节点到叶节点的权值最大路径，对于当前节点到叶节点的路径与之前如何到达当前节点没有关系，只要计算当前节点到叶节点的路径，就一定是重复的计算，可以直接返回结果。作为反例，在一个字母矩阵当中寻找词典中的单词，当前路径能否构成单词，不仅与之后走的过程有关，也与之前的过程有关。因此，从当前节点出发，哪怕走过相同的路径，也不能看成是重复计算的子问题。在回溯部分我们会进一步讲解。

用回溯法( 自上而下 )解决发散结构问题

对于发散性问题(例如“所有组合”，“全部解”)，可以选取其问题空间“收敛”的一端作为起点，沿着节点发散的方向(或者说，当前节点的多种选择)进行递归，直到

当前节点“不合法” 或
当前节点发散方向搜索完毕，才会return

举例来说，考虑树的遍历：根节点方向就是“收敛”的一端，节点发散的方向就是子节点。对于某个树的节点，其孩子就是当前决策的多种选择。当达到叶节点是，其孩子为NULL，即达到“不合法”的边界条件。回溯法的核心在于选择哪些方向/决策，才是最合理，不重复的。所谓“剪枝”(pruning)，就是指：只选择尽可能少的、可能到达“胜利条件”的方向，而不是搜索当前节点的所有发散方向。这样，可能将幂指数级的复杂度降低到阶乘级。

值得注意的是，invalid前的最末节点未必意味着胜利(不是所有的问题走通就算满足条件)，胜利的节点也未必代表不需要继续走下去(比如寻找到一个单词之后，继续走下去可能能找到以这个单词为前缀的另一个单词)。因此我们强烈推荐将invalid的判定与胜利条件的判定总是分开，即使在某些题目中它们是一致的。当然，如果经过充分剪枝之后，所有搜索只会沿着“正确”的方向行进，那么当前节点“不合法”往往也就意味着胜利条件。

如果需要记录决策的路径，可以用vector<int> &path沿着搜索的方向记录，在满足胜利条件时记录当前path(通常是将path存入vector<vector<int>> &paths)。

注意，我们传入的path是引用形式，属于全局变量。Backtracking(回溯)本身隐含的含义是，在访问完这个节点返回时，需要恢复原本的状态(即回到该节点)，以访问其他路径。具体实现时，意味着需要:

在return前，删除path中的当前节点。
如果搜索的方向有出现环路的可能，那么可以使用bool []或unordered_map来记录该节点是否已被使用，在访问时以及return前维护。

如果以传值形式传入path，由于path成了局部变量，故在某些情况下不需要显式回溯，相当于把状态复制给了子问题。可能有人觉得这样做比较直观，但其缺点是需要额外的空间。

回溯法的典型模板如下所示：

void backtracking( P node, vector<P> &path, vector<vector<P> >&paths ){
        if(!node )  // invalid node
            return;

        path.push_back(node);

        bool success =  ;  // condition for success
        if( success )  
            paths.push_back( vector<P>(path.begin(),path.end()) ); 
            // don't return here
        
        for( P next: all directions )
            backtracking( next, path, paths );
        path.pop_back();
        return;
}

用Divide and Conquer 解决独立子问题

如果能将问题由几个孤立但类似的部分组成，则可以优先选择使用D&C策略：将问题分割解决，再合并结果。特别地，如果期望将问题的复杂度由O(n)进一步降低到O(logn)，一般总是可以联想到使用D&C策略，将问题分割而治。

从子问题得到最终解

递归和动态编程能解决的问题都有一个特性：原问题(problem)可以分解成若干个子问题(sub-problem)，只有先解决了子问题才能进一步解决原问题。子问题的解决方式形式上与原问题一致。从题目描述来看，可以提示我们尝试用递归、DP解决的关键词有：compute nth element (value, sum, max, etc.), return all the paths, return all the combinations, return all the solutions…

既然动规与递归都能解决相同类型的问题，那么DP和递归有什么不同？最大的区别在于，DP存储子问题的结果，当子问题已经被计算过，直接返回结果。因此，当需要重复计算子问题时，DP的时间效率高很多，但需要额外的空间。

特别地，具有聚合属性的问题(Aggregate)，例如在所有组合中寻找符合特定条件的特解(比如二叉树求一条从根节点到叶节点和为定值的路径，或第n个元素)，或最优解(包括最值)，或总和，或数量的问题(其实看一下SQL里的聚合函数(aggregate function)就明白了)。因为这些问题它们只需要一个聚合的或者特殊的结果，而不是所有满足条件的集合，所以它们具有很强的收敛性质。这类问题往往也可以用DP来解决。

本章节将问题处理的每一个最小的元素/步骤，称为节点，就好比一维/二维/三维数组中的一个element，或者每一次递归中独立解决的那个元操作。我们把节点空间“两端收敛”的问题，归结为收敛结构；将节点空间“发散”的问题，归结为发散结构。形象地说，收敛问题是由若干个子问题共同决定当前状态，即状态的总数逐渐“收敛”，例如斐波那契数列问题(前两个节点决定当前节点)；发散问题是当前状态会衍生出多个下一状态，例如遍历已知根节点的二叉树(下一层的状态以指数形式增加)。抽象地说，能够在多项式时间内解决的问题，是收敛问题(P类问题)，不能在多项式内解决的问题(如阶乘级或指数级)，是发散问题(NP类问题)。定义“收敛”和“发散”是为了方便本章节描述和区分这两类问题，并非是公认的准则。

递归的空间与时间成本

对系统层面上说，操作系统是利用函数栈来实现递归，每次操作可视为栈里的一个对象。递归的时间成本随递归深度n(单条路径中递归调用的次数)成指数增长；空间复杂度为O(n)。

自底向上与自顶向下

从子问题解决原问题, 无非是两种方法，自底向上(Bottom-Up)与自顶向下(Top-Down)，形式上前者对应iteration，利用循环将结果存在数组里，从数组起始位置向后计算；后者对应recursion，即利用函数调用自身实现，如果不存储上一个状态的解，则为递归，否则就是DP。举个斐波那契数列(0,1,1,2,3,5…)的例子：

1) 自底向上

int array[n] = {0};
array[1] = 1;
for (int i = 2; i < n; i++)
    array[i] = array[i-1] + array[i-2];

这里，为了说明方法，采用数组存储结果，空间复杂度O(n)。事实上，额外空间可以进一步缩小到O(1)：利用几个变量记录之前的状态即可。由于我们记录了子问题的解，故给出的方法就是DP。事实上，自底向上的方式往往都是通过动态编程实现。

2) 自顶向下

int Fibonacci(int n)
{
    if(n == 0)
        return 0;
    if(n == 1)
        return 1;
    return Fibonacci(n-1) + Fibonacci(n-2);
}

为计算Fibonacci的第n个元素，我们先自顶向下地计算子问题：第n-1个元素和第n-2个元素。由于没有存储子问题的运算结果，我们给出的方法是递归。然而，Fibonacci(n-1)与Fibonacci(n-2)包含很多重复的子问题，所以DP效率更高。如果用一个全局数组，将子问题的解存储到数组的对应位置，在重复计算的时候直接读取计算结果，那么就是DP的解法。

我们再次强调：动态编程的核心在于，如果在一个问题的解决方案中，子问题被重复计算，那么就可以利用记录中间结果，达到用空间换取时间的目的。

以下如不额外说明，动态编程特指迭代形式的自底向上的动态编程，并将自顶向下，递归形式，在递归过程中用哈希表记录中间计算结果的DP，称作Memorization。

Memorization的一般形式是: 建立以input为键，以output为value的哈希表：

T func(N node, HashTable<N, T>& cache) {
    If (cache.contains(node)) {
        return cache.get(node);
    }
    …
    T sub_res = func(next_node, cache);
…
    T res = G( sub_res … );  //当前子问题的解，依赖于更小的子问题(s)
    cache.set(node, res);
    return res;
}

从解决问题的角度来说，用自底向上的DP，固然通常可以节省递归本身的空间开销，但有很多缺点和局限：较难理解，边界条件较难处理，只适用于问题的节点空间是离散的整数空间，必须一步步邻接、连续地计算(无论是不是每一个节点的结果都会被用到)。而Memorization，则灵活得多：可以从递归形式轻易修改得到，也更符合普遍的思维过程，并且没有上面说的这些局限，子问题只有在被需要的时候才会被计算。尤其是在某些情况下，不仅需要aggregate的结果，还需要获得achieve这个结果的路径，这时候就算用自底向上的DP，也需要记录prev节点，最后需要递归回溯得到路径，那么节省递归空间开销的优势，也荡然无存了。

尽管有上述局限, 自底向上的DP，仍然可以作为很好的思维和编程训练，熟练之后写法也很简洁精妙，本章节也会举很多例子，但完全不用过于痴迷这类技巧性较强的解法，否则就是买椟还珠了。毕竟，从面试的角度讲，在这么短时间内，期望面试者用这类DP解法写出一个完整程序，并不是非常普遍的。

算法策略

以下回顾一些利用到DP思想的经典算法策略：

分而治之(Divide and Conquer)
- 这里只谈狭义的D&C，即将问题分成几个部分，每一部分相互独立，互不重叠，假定每个部分都可以得到解决来进行递归调用，合并每一部分的结果。
- 例如Merge Sort， Quick Sort (Merge Sort的divide容易，但Conquer/Merge复杂，Quick Sort的divide复杂，但Conquer/Merge容易)
动态编程(Dynamic Programming)
- 尽可能不重复计算每个子问题，而是将计算结果存储下来，以确定后驱问题的解。
- 与贪心算法的区别是，会记录下所有可能通向全局最优解的局部解，以便在计算后驱问题时综合考虑多个前驱问题的解。
贪婪算法(Greedy Algorithm)
- 只做出当下最优的判断，并且以此为基础进行下一步计算。当前判断最优时，不考虑对全局/未来的影响，所以所以从全局来说并不能保证总是最优。
- 贪心算法每次更新当前的最优解。如Dijkstra算法就是贪心算法的实例之一。
回溯 (Backtracking)
- 一种暴力(穷举)的深度优先搜索法：搜索，直到节点空间的尽头，然后再返回到上次的节点，再往其他方向深度搜索。
- 树或图的DFS是回溯的实例之一。