浅谈动态规划（三）——找到最优时的解

By | 2016年12月4日
0 Comment

前两次动态规划的博客中，介绍了动态规划最基础的两个特点以及列举了几个我在做lintcode中遇到的接触动态规划初期相对比较适合做的题目。这次结合几道题目来总结一下动态规划的另一个特点——找到最优时的解。

同样，还是以题目来说明。

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

题目给出了一个数组A，并且给出了一个目标数字target。要求调整数组中每个位置的数字得到数组B，使得数组B中相邻元素的差值的绝对值小于等于target，且$$sum(|A[i] – B[i]|)$$最小。求得到最终结果时每个位置调整的和最小为多少。

题目只要求找出最小的调整开销的和，我这里再加一问：在调整和为最小值时，找出一个可能的数组B。

先来解决lintcode要求的问题。

Minimum Adjustment Cost题解:

我们应该能够想通一个问题，调整后的每个位置的数字都是在A数组中出现的最小值与最大值之间的数字。假设最小值是minVal，最大值是maxVal，所以数组B的每个位置上可选择的数字的个数为$$count = maxVal – minVal + 1$$。

构造一个二维数组$$cost[n+1][count]$$，n表示数组A中的个数。$$cost[loop][j]$$$$(0 <= loop <= n, minVal <= j <= maxVal)$$表示B数组中第loop个位置上（此时B的下标为loop-1）调整为数字j时的调整总和（包括loop之前的所有位置的调整的和）。那么当调整下一个位置loop+1时，调整为数字i的调整总和为$$cost[loop+1][i] = min(cost[loop][j] + | i – A[loop] |)$$,$$|i – j| <= target$$。这里j是上一个位置时调整的结果，因为有限制条件相邻的两个元素差的绝对值小于target，所以要用到上一个位置的数组；$$|i – A[i]|$$是此位置（数组B中第loop+1个数字，下标为loop）调整为i时调整的代价。最后的结果是$$cost[n][i]$$$$(minVal <= i <= maxVal)$$中最小的值。

可能我的表述不太清楚，加注释的代码可能表达的更清楚些：

int MinAdjustmentCost(vector<int> A, int target)
{
	int n = A.size();

	if (n <= 0 || n == 1)
		return 0;

	int minVal = INT_MAX; // 记录数组中最小值
	int maxVal = INT_MIN; // 记录数组中最大值
			
	int loop, i, j;
	
	// 找出数组A中出现的最小值和最大值
	for (i = 0; i < n; i++) { if (A[i] > maxVal)
			maxVal = A[i];
		if (A[i] < minVal)
			minVal = A[i];
	}
	
	int count = maxVal - minVal + 1; // 每次需要动态规划的个数
	// 辅助数组。记录每个位置上B调整为不同数字的最小开销。
	// 即，当B数组第loop个数字调整为i的时候的最小开销为cost[loop][i]
	vector<vector<int> > cost(n+1, vector<int>(count, INT_MAX)); 
	// 初始化
	for (i = 0; i < count; i++)
		cost[0][i] = 0; 

	// 动态规划步骤
	for (loop = 1; loop <= n; loop++)
	{
		// 找出数组B中，第loop个位置（下标为loop-1），选择数字i的最小调整代价
		// 即，找出cost[loop][i]。它记录了到loop位置时，调整为i数字的最小开销
		for (i = minVal; i <= maxVal; i++)
		{
			for (j = minVal; j <= maxVal; j++)
			{
				if (abs(i-j) <= target)
				{
					int temp = cost[loop-1][j-minVal] + abs(i-A[loop-1]); // 当第loop-1个数字选择j时，第loop个数字选择（调整到）i时的改变量
					if (temp < cost[loop][i-minVal]) // 找出最小的调整代价
						cost[loop][i-minVal] = temp;
				}
			}
		}
	}

	// 找出最后一个位置改变结束时最小的改变代价
	int minCost = INT_MAX;
	for (i = 0; i < count; i++)
		minCost = min(cost[n][i], minCost);

	return minCost;
}

我们发现，在每次比较找出最小开销的时候，可以在加一个辅助数组$$record[n+1][count]$$,记录每个位置时最小调整开销时选择的数字，最后得到了完整的cost列表之后，$$cost[n][i]$$$$(minVal <= i <= maxVal)$$中最小时i的值就是B[n-1]中的值，然后$$record[n][i]$$中记录的即使上一个位置对应的B中的值，以此类推，便能找到B数组一个可能的结果。同样，看代码可能更清楚点:

// 实现了记录每次选择数字的功能
void MinAdjustmentCost(vector<int> A, int target)
{
	int n = A.size();

	if (n <= 0 || n == 1)
		return;

	int minVal = INT_MAX; // 记录数组中最小值
	int maxVal = INT_MIN; // 记录数组中最大值
			
	int loop, i, j;
			
	for (i = 0; i < n; i++) { if (A[i] > maxVal)
			maxVal = A[i];
		if (A[i] < minVal)
			minVal = A[i];
	}
	
	int count = maxVal - minVal + 1; // 每次需要动态规划的个数
	vector<vector<int> > cost(n+1, vector<int>(count, INT_MAX)); // 辅助数组
	vector<vector<int> > record(n+1, vector<int>(count, 0));
	vector<int> B(n);
	// 初始化
	for (i = 0; i < count; i++)
		cost[0][i] = 0; 

	// 动态规划步骤
	for (loop = 1; loop <= n; loop++)
	{
		// 找出第loop个位置，选择数字i的最小调整代价
		for (i = minVal; i <= maxVal; i++)
		{
			for (j = minVal; j <= maxVal; j++)
			{
				if (abs(i-j) <= target)
				{
					int temp = cost[loop-1][j-minVal] + abs(i-A[loop-1]); // 当第loop-1个数字选择j时，第loop个数字选择（调整到）i时的改变量
					if (temp < cost[loop][i-minVal]) // 找出最小的调整代价
					{
						cost[loop][i-minVal] = temp;
						record[loop][i-minVal] = j; // record中记录的是第loop个数字取i最优时，上一个数字最优时对应的值
					}
				}
			}
		}
	}

	// 找出最后一个位置改变结束时最小的改变代价
	int minCost = INT_MAX;
	int backtrack; // 用于回溯之前的一个位置应该调整为哪个数值
	for (i = minVal; i <= maxVal; i++)
	{
		if (cost[n][i-minVal] < minCost)
		{
			minCost = cost[n][i-minVal];
			backtrack = i; // 找到最后一个调整好的数值对应的前一个数值
		}
	}

	cout << minCost << endl; // 输出最小的调整代价 int loc = n - 1; // 对应数组B每个下标 int sum = 0; // 用于核对回溯的每个位置的值是否正确，minCost == sum时正确 while (n > 0)
	{
		B[loc--] = backtrack;
		sum += abs(A[n-1] - backtrack);
		backtrack = record[n--][backtrack-minVal]; // 因为每次找到的调整好的数值，所以索引要调整
	}
	cout << sum << endl; // 比较sum是否等于minCost

	// 输出调整之后的数组B
	for (i = 0; i < A.size(); i++)
		cout << B[i] << ' ';
	cout << endl;
}

2.钢条切割问题

接下来我们再来看一下《算法导论》上给的一道经典题目，钢条切割问题。

题目描述：

一家公司有一根固定长度的钢条，要切割为短的钢条出售。切割工序本身没有成本。公司希望知道最佳的切割方案（即如何切割能够获得价格的最大值）。假设钢条的长度为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)$$，那么当长度为i+1时，最佳的方案是$$r[i+1] = max(p[j] + r[i+1-j]), 1<= j <= i+1$$。所以状态转移方程即是：
$$!r[i+1] = max(p[j] + r[i+1-j]),1<= j<= i+1$$
同样，看代码可能思路更清晰：

// 自底向上实现
// 数组p记录不同长度的价格，n是所求最大的长度
int cutRodBottomUp(vector<int> const &p, int n)
{
	vector<int> r(n+1, INT_MIN); // 辅助数组，记录每个长度不同切割方法的最大值。以整型最小值初始化
	r[0] = 0; 

	// 动态规划每个长度不同切割方法的最大值
	for (int i = 1; i <= n; i++)
	{
		int q = INT_MIN;
		for (int j = 1; j <= i; j++)
		{
			q = max(q, p[j-1] + r[i-j]);  // 找到每个长度切割的最大值。上述解释中的j是长度，j-1对应其下标
		}
		r[i] = q;
	}

	return r[n];
}

这时函数返回的是最大的长度，再加一个辅助数组，在每次找出最大价值的时候记录切割位置，就可以找出切割方案了。代码如下：

// 带有输出分割情况功能的版本
void cutRodExtended(vector<int> const &p, int n)
{
	vector<int> r(n+1, INT_MIN); // 辅助数组，记录每个长度不同切割方法的最大值
	r[0] = 0;
	vector<int> s(n+1, 0); // 记录每个长度最大收益时的切割位置
	
	int i, j;

	// 动态规划步骤
	for (i = 1; i <= n; i++)
	{
		int q = INT_MIN;
		for (j = 1; j <= i; j++)
		{
			if (q < p[j-1] + r[i-j])
			{
				q = p[j-1] + r[i-j];
				s[i] = j; // 记录每个长度最大收益时的切割位置
			}
			r[i] = q;
		}
	}

	cout << r[n] << endl; // 输出结果 while (n > 0)
	{
		cout << s[n] << '\t';
		n = n - s[n];
	}
	cout << endl;
}

这样，就找到最佳切割方案了。

3.最长公共子序列

最后，再来看另一道《算法导论》里面的经典问题——最长公共子序列，这到题目也非常适合用辅助数组来记录最优解。

题目描述：

给定两个序列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。

解题思路：

我们假设Z = {$$z_1$$, …, $$z_k$$}是X和Y的一个最长公共子序列。1）如果$$x_m$$ == $$y_n$$，那么有$$z_k$$ == $$x_m$$ == $$y_n$$，所以$$Z\_{k-1}$$是$$X\_{m-1}$$和$$Y\_{n-1}$$的一个最长公共子序列；2）如果$$x_m$$ != $$y_n$$且$$x_m$$ != $$z_k$$，那么Z是$$X_{m-1}$$和Y的一个最长公共子序列；3）如果$$x_m$$ != $$y_n$$且$$z_k != y_n$$，那么Z是X和$$Y_{n-1}$$的一个最长公共子序列。

我们令$$c[i][j]$$表示$$X_i$$和$$Y_j$$的最长公共子序列的长度，那么可以得到以下关系：

情况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(vector<char> &X, vector<char> &Y)
{
	int len1 = X.size();
	int len2 = Y.size();
	int i, j;

	vector<vector<int> > c(len1+1, vector<int>(len2+1)); // 辅助二维数组，记录$X_i$, $Y_j$的最长公共子序列
	
	// 初始化
	for (i = 0; i <= len1; i++)
		c[i][0] = 0;
	for (j = 0; j <= len2; j++)
		c[0][j] = 0;

	// 动态规划过程
	for (i = 1; i <= len1; i++)
	{
		for (j = 1; j <= len2; j++) { if (X[i-1] == Y[j-1]) // 对应状态转移方程中情况2 c[i][j] = c[i-1][j-1] + 1; else if (c[i-1][j] > c[i][j-1]) // 对应状态转移方程中情况3
				c[i][j] = c[i-1][j];
			else // 对应情况3
				c[i][j] = c[i][j-1];
		}
	}

	return c[len1][len2];
}

在情况2和情况3的判断中，可以加入判断结果，将结果记录到一个辅助数组，这样就能回溯结果了，代码如下：

// 自底向上动态规划。path二维数组记录对应X_i, Y_j的最长公共子序列的选择情况。
// 自底向上动态规划。path二维数组记录对应X_i, Y_j的最长公共子序列的选择情况。
int LCS2(vector<char> &X, vector<char> &Y,vector<vector<string> > &path)
{
	int len1 = X.size();
	int len2 = Y.size();
	int i, j;

	vector<vector<int> > c(len1+1, vector<int>(len2+1)); // 记录对应位置的结果
	
	// 初始化
	path.resize(len1+1);
	for (i = 0; i <= len1; i++)
		path[i].resize(len2+1);

	for (i = 0; i <= len1; i++)
		c[i][0] = 0;
	for (j = 0; j <= len2; j++)
		c[0][j] = 0;

	// 动态规划过程
	for (i = 1; i <= len1; i++)
	{
		for (j = 1; j <= len2; j++) { if (X[i-1] == Y[j-1]) { c[i][j] = c[i-1][j-1] + 1; path[i][j] = "left-top"; // 上一个位置在左上位置 } else if (c[i-1][j] > c[i][j-1])
			{
				c[i][j] = c[i-1][j];
				path[i][j] = "up"; // 上一个位置在上方
			}
			else
			{
				c[i][j] = c[i][j-1];
				path[i][j] = "left"; // 上一个位置在左边
			}
		}
	}

	return c[len1][len2];
}

这里配合下图更好理解。

这里的根据路径输出的函数为：

void Print_LCS(vector<char> &X, vector<vector<string> > &path, int i, int j)
{
	if (i == 0 || j == 0)
		return;

	if (path[i][j] == "left-top") // 左上位置
	{
		Print_LCS_test(X, path, i-1, j-1);
		cout << X[i-1];
	}
	else if (path[i][j] == "up") // 上方
		Print_LCS_test(X, path, i-1, j);
	else if (path[i][j] == "left") // 左边
		Print_LCS_test(X, path, i, j-1);
}

参考文献：
1.lintcode Minimum Adjustment Cost。
2.《算法导论（第三版）》，15章，动态规划内容。

发表评论

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

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