从lintcode做题的角度来说，递归往往会开销较大。不过在做动态规划的时候，我们能发现递归是个不错的工具，对于解决问题的代码量能够缩小很多。同时，如果使用了带有备忘的递归，能够减少很大的开销。这次列举几个典型的使用带备忘的递归的例子，来总结一下带备忘的递归的使用。这篇文章中的三个题目均是上篇博客中出现过的，便于比较。

首先我们来看第一题。

1.钢条切割

题目描述：

一家公司有一根固定长度的钢条，要切割为短的钢条出售。切割工序本身没有成本。公司希望知道最佳的切割方案（即如何切割能够获得价格的最大值）。假设钢条的长度为n（此处假设n <= 10），不同长度i的钢条的价格如下表。

长度j12345678910
价格p1589101717202430


假设长度为i时，最佳切割方案时的价格总和为$r[i]$$(0 <= i<= n)$，根据上篇博客所说，此题目的状态转移方程为：

$r[i+1] = max(p[j] + r[i+1-j]),1<= j<= i+1$

这样，便很容易写出递归的代码：
1
2
3
4
5
6
7
8
9
10
11
12
// 不带备忘的递归版本
int cutRod(vector<int> &p, int n)
{
	if (n == 0) // 递归出口，当n == 0的时候收益为0
		return 0;
	int q = INT_MIN;
	for (int i = 1; i <= n; i++)
		q = max(q, p[i-1] + cutRod2(p, n-i)); // 状态转移，递归找出每次的最大值
	return q;
}

大家都知道，使用递归时，往往会因为不断的求解之间已经解决过的问题而使用更多的空间，那么有没有好办法能解决这个问题呢？那么用备忘来记录中间求解过的值就能够解决。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 使用备忘的递归版本。使用备忘之后能减少很多开销
int cutRod(vector<int> &p, int n)
{
	vector<int> r(n+1, INT_MIN); // 增加一个数组，记录中间已经求解过的结果
	r[0] = 0;
	return cutRodAux(p, r, n);
}
 
// 辅助函数
int cutRodAux(vector<int> &p, vector<int> &r, int index)
{
	if (r[index] != INT_MIN) // 递归出口。如果此时数组中的元素不为INT_MIN，意味着已经求解，直接返回即可。
		return r[index];
	// 如果数组中的元素是INT_MIN，那么需要递归求解
	int q = INT_MIN;
	for (int i = 1; i <= index; i++)
		q = max(q, p[i-1] + cutRodAux(p, r, index-i));
	r[index] = q; // 将递归求解的结果记录到数组
	return q;
}

接下来再看下一题。

2.最长公共子序列

题目描述：

给定两个序列X = {$x_1$, $x_2$, $x_3$, …, $x_m$ }, 和Y = {$y_1$, $y_2$, …, $y_n$}，求X和Y长度最长的公共子序列。公共子序列的定义为，给定两个序列X，Y，如果Z即是X的子序列，也是Y的子序列，我们称它是X和Y的公共子序列。

例如：X = {A, B, C, D, A, B}，Y = {B, D, C, B, A}，那么序列｛B, C, A｝就是X和Y的公共子序列，但不是最长公共子序列。X和Y的最长公共子序列是{B, C, A, B}，其长度为4。

根据上篇文章，状态转移方程为：

情况1: $i==0$ 或者 $j== 0$时，$c[i][j] = 0$;
情况2: $i, j > 0$且$x_i$ == $y_j$时， $c[i][j] = c[i-1][j-1] + 1$;
情况3: $i，j > 0$且$x_i != y_j$时， $c[i][j] = max(c[i][j-1], c[i-1][j])$;

那么直接用递归实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int LCS(string A, string B)
{
	int len1 = A.length();
	int len2 = B.length();
	return LCS_AUX(A, B, len1, len2);
}
int LCS_AUX(string A, string B, int idx1, int idx2)
{
	if (idx1 == 0 || idx2 == 0) // 递归出口，情况1
		return 0;
	if (A[idx1-1] == B[idx2-1])
		return LCS_AUX(A, B, idx1-1, idx2-1) + 1; // 情况2
	else
		return max(LCS_AUX(A, B, idx1-1, idx2), LCS_AUX(A, B, idx1, idx2-1)); // 情况3
}

同样，加入备忘，记录过程中的求解的值，就可以节省很多开销。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int LCS(string A, string B)
{
	int len1 = A.length();
	int len2 = B.length();
	vector<vector<int> > c(len1+1, vector<int>(len2+1, INT_MAX));
	//for (int i = 0; i <= len1; i++)
	//	c[i][0] = 0;
	//for (int j = 0; j <= len2; j++)
	//	c[0][j] = 0;
	return LCS_AUX(A, B, c, len1, len2);
}
int LCS_AUX(string A, string B, vector<vector<int> > &c, int idx1, int idx2)
{
	if (idx1 == 0 || idx2 == 0) // 递归出口，情况1
		return 0;
	if (c[idx1][idx2] != INT_MAX) // 如果已经求解过，那么直接调出之前的结果
		return c[idx1][idx2];
	if (A[idx1-1] == B[idx2-1]) // 情况2
		c[idx1][idx2] =  LCS_AUX(A, B, c, idx1-1, idx2-1) + 1; // 更新辅助数组中此处的值，便于以后调出
	else
		c[idx1][idx2] =  max(LCS_AUX(A, B, c, idx1-1, idx2), LCS_AUX(A, B, c, idx1, idx2-1)); // 情况3
	return c[idx1][idx2];
}

3.Minimum Adjustment Cost

题目描述：

Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target.If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|

Notice: You can assume each number in the array is a positive integer and not greater than 100.

Example: Given [1,4,2,3] and target = 1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it’s minimal.

第三题有点难度，是深度优先搜索的思想，解释的话有些太费时间，不过如果手动着算一下，结合我代码的注释，也能比较容易就看懂，所以直接上代码，具体的解析见上篇博客。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// 深度优先查找，用递归。此方法比之前类似广度查找的方法的好处是，可以查找所有可能的情况
int MinAdjustmentCost(vector<int> A, int target)
{
	if (A.size() == 0)
		return 0;
	// 找到最小值和最大值
	int minVal = INT_MAX;
	int maxVal = INT_MIN;
	for (int i = 0; i < A.size(); i++)
	{
		minVal = min(minVal, A[i]);
		maxVal = max(maxVal, A[i]);
	}
	// 初始化辅助数组，每个位置记录从后到前调整的代价
	vector<vector<int> > M(A.size(), vector<int>(maxVal - minVal + 1, INT_MAX));
	vector<int> B(A); // 数组B记录了每次尝试的结果
	// 调用辅助函数
	return MinAdjustmentCostAux(A, B, target, 0, M, minVal, maxVal);
}
// 辅助函数，实现带有表格的递归，从而减少运行次数
// 返回下标为index时，与前一个数字在target限定范围内的最小调整代价
int MinAdjustmentCostAux(vector<int> A, vector<int> B, int target, int index, vector<vector<int> > &M, int minValue, int maxValue)
{
	int n = A.size();
	if (index >= n)
		return 0;
	int dif = 0;
	int minCost = INT_MAX;
	for (int i = minValue; i <= maxValue; i++)
	{
		if (index != 0 && abs(i - B[index-1]) > target)
			continue;
		// 如果查找时发现此位置已经有结果，那么直接返回
		if (M[index][i-minValue] != INT_MAX)
		{
			dif = M[index][i-minValue];
			minCost = min(minCost, dif);
			continue;
		}
		// 此时index位置的值尝试为i
		B[index] = i;
		dif = abs(i - A[index]); // 计算此位置调整的代价
		dif += MinAdjustmentCostAux(A, B, target, index + 1, M, minValue, maxValue); // 加上后面所有数调整的代价，得到的是总代价
		minCost = min(minCost, dif); // 找到每个数字调整的最小代价
		M[index][i-minValue] = dif; // 记录到辅助数组M中，实现减少运行次数
		B[index] = A[index]; // 用于回溯
	}
	return minCost;
}

比较一下，是不是使用带有备忘的递归会使得程序简单很多呢？