浅谈动态规划（四）——巧用递归

内容简介：浅谈动态规划（四）——巧用递归

从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)$ ，根据上篇博客所说，此题目的状态转移方程为：

这样，便很容易写出递归的代码：

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

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

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

• 算法-动态规划
• 聊聊动态规划(2) -- 特征
• 聊聊动态规划(1) -- 概念
• Golang动态规划
• leetcode题解(动态规划)
• leetcode题解(动态规划)

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。