背景

在解决问题的过程中，我们经常需要对大问题进行拆分，分而治之。

拆分的时候通常是根据特殊对象等进行分类。 在树中考虑根节点，在实际问题中考虑最后一个，最特殊的一个等等。 本篇讲解一下此类思路。

组合的递推公式

n个数里面选m个数的组合，我们用f[n][m]表示。 那么有f[n][m] = f[n - 1][m - 1] + f[n - 1][m]

我们给一个实际场景：班里有n名同学，现在要选m个同学去春游。 我们考虑班长这个特殊的对象，进行分类讨论。

• 班长去，那么需要在剩下的n-1个人里分配m-1个名额。即为f[n - 1][m - 1]。
• 班长不去，那么需要在剩下的n-1个人里分配m个名额。即为f[n - 1][m]。 两种情况合并就是原问题的解。

相比于f[n][m]来说，f[n - 1][m - 1]和f[n - 1][m]都是规模更小的问题。 我们成功地实现了“大事化小”，拆分问题。

二叉树的形态数

请问n个结点的二叉树有多少种形态。

如上图所示，3个结点的二叉树有5种形态。我们把根结点拿出来，其实你会发现剩下的2个结点有3种分配方式。

左 右
2  0
1  1
0  2

我们用f(n)表示n个结点的二叉树形态数。 f(3) = f(2) * f(0) + f(1) * f(1) + f(0) * f(2)

其实符合这样一个递推公式的数列叫做卡特兰数。 卡特兰数的典型例子还有：对角线蚂蚁问题、凸多边形划分问题等。

打家劫舍 I

打家劫舍 (opens new window)

给定一个长度为n的数组a，数组中有一些正整数，表示n个房间，及其中财物的价值。这个聪明的小偷呢，可以选择不相邻的房间偷取。 请问它最多能偷到多少价值的财物。

我们用f[i]表示偷前i个房间能够达到的最大价值。 考虑第i个房间偷不偷：

• 偷第i个房间，则i-1房间不能偷，只能拿前i-2个房间偷到的最大价值加上当前房间财宝价值。f[i - 2] + a[i]。
• 不偷第i个房间，则取偷前i-1个房间能够拿到的最大价值。即为f[i - 1]。 对于f[i]，取上述两种情况的最大值即可。

背包问题（二维）

我们考虑一个基本的01背包问题，写出基本的状态计算方式。 背包容量为m，有n个物品，体积为，每个物品只有1个，求问背包最多能放多少体积的物品？

我们用f[i][j]表示前i个物品装入体积为j的背包中最多能放的体积，最终要求的就是f[n][m]。 对于f[i][j]，我们以最后一个物品(第i个物品)来做分类讨论。

• 装第i个物品 f[i - 1][j - v[i]] + v[i]
• 不装第i个物品 f[i - 1][j] 我们只需要在上述两种情况中求最大值，就是f[i][j]的结果。