跳转至

递归 & 分治

递归

介绍分治之前,首先要弄清楚递归这个概念。

递归是什么呢?举个简单的例子:从前有座山,山上有座庙,庙里有个老和尚,老和尚给小和尚讲故事:“从前有座山,山上有座庙,庙里有个老和尚,老和尚给小和尚讲故事:‘从前有座山......’” 这个故事与递归算法有着异曲同工之妙。

递归的基本思想是某个函数直接或者间接地调用自身,这样就把原问题的求解转换为许多性质相同但是规模更小的子问题。我们只需要关注如何把原问题划分成符合条件的子问题,而不需要去研究这个子问题是如何被解决的。

递归和枚举的区别在于:枚举是横向地把问题划分,然后依次求解子问题,而递归是把问题逐级分解,是纵向的拆分。

递归三要素

在用递归思想解题的时候,要考虑三个要素。

递归式

如何将原问题划分为子问题?如何科学地进行递归?

递归出口

终止的条件是什么?换言之,最小的子问题是怎么求解的。

出口可以不止一个。

界函数

我们用一个函数来表示问题规模变化,这个函数需要保证递归的条件是在像出口条件靠拢。

递归模板

1
2
3
4
int f(传入数值) {
  if (终止条件) return 最小子问题解;
  return f(缩小规模);
}

递归优化

先来一道例题:三连击

这道题朴素的递归写法只能得到 25 分,因为递归次数太多,所以超时。

怎么优化呢?详见 搜索优化记忆化搜索

分治

分治是一种极为重要的思想。顾名思义,分而治之,就是把大问题化小,再各个击破的过程。

英文名是 divide and conquer.

例题

求数列中有多少个逆序对,所谓逆序对,是满足 i < j 而且 a[i] > a[j] 的数对 (i, j) 的个数。

考虑把数列等分成两部分,那么原数列的逆序对有两种情况:一种是两个数完全包含在某一侧的子数列中,另一种是两个数一左一右被分开了。

不难发现前者只需要递归地求出,后者只需要对于左侧的每个数,统计右侧有多少个比它小的。


评论