浅谈动态规划(四)——巧用递归

By | 2017年1月11日

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

首先我们来看第一题。

1.钢条切割

题目描述:

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

长度j

1

2

3

4

5

6

7

8

9

10

价格P

1

5

8

9

10

17

17

20

24

30

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

这样,便很容易写出递归的代码:

// 不带备忘的递归版本
// 不带备忘的递归版本
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;
}

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

// 使用备忘的递归版本。使用备忘之后能减少很多开销
// 使用备忘的递归版本。使用备忘之后能减少很多开销
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.最长公共子序列

题目描述:

根据上篇文章,状态转移方程为:

情况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])$$;

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

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
}

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

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]|.

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.

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

// 深度优先查找,用递归。此方法比之前类似广度查找的方法的好处是,可以查找所有可能的情况
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;
}

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

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据