0%

【编程起跑线】06 递归与动态规划

递归和动态规划应该算是算法问题中的难点。核心解法很简单,就是要找到状态转移方程,也就是如何把原问题分解成子问题,然后分而治之。所以说,更多像是一种思维方式,而不是具体的步骤技巧。


更新历史

  • 2019.08.05:编入新系列
  • 2016.01.23:完成初稿

解题策略

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

具有强收敛性属性的问题(特解,或最值,或总和,或数量的问题),都可以用整数坐标映射所有节点,且当前节点的解只依赖于前驱节点(无论是顺序还是倒序)。那么,这类问题往往可以用DP解决。解决的关键是建立子问题的解之间的递推关系:

其中 G[ ] 表示子问题到原问题的映射关系,例如对于斐波那契数列,有递推式:

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

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

注意,如果出现类似于“所有解”,“所有路径”等关键词,则用自上而下方法更为直接。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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类问题)。定义“收敛”和“发散”是为了方便本章节描述和区分这两类问题,并非是公认的准则。

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

算法策略

以下回顾一些利用到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是回溯的实例之一。

附录