前两次动态规划的博客中,介绍了动态规划最基础的两个特点以及列举了几个我在做lintcode中遇到的接触动态规划初期相对比较适合做的题目。这次结合几道题目来总结一下动态规划的另一个特点——找到最优时的解。
同样,还是以题目来说明。
题目描述: 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.
题目给出了一个数组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)$中最小的值。
可能我的表述不太清楚,加注释的代码可能表达的更清楚些: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
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;
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));
for (i = 0 ; i < count; i++)
cost[0 ][i] = 0 ;
for (loop = 1 ; loop <= n; loop++)
{
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 ]);
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
数组一个可能的结果。同样,看代码可能更清楚点: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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
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++)
{
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 ]);
if (temp < cost[loop][i-minVal])
{
cost[loop][i-minVal] = temp;
record[loop][i-minVal] = j;
}
}
}
}
}
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 ;
int sum = 0 ;
while (n > 0 )
{
B[loc--] = backtrack;
sum += abs (A[n-1 ] - backtrack);
backtrack = record[n--][backtrack-minVal];
}
cout << sum << endl ;
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$ 同样,看代码可能思路更清晰:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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]);
}
r[i] = q;
}
return r[n];
}
这时函数返回的是最大的长度,再加一个辅助数组,在每次找出最大价值的时候记录切割位置,就可以找出切割方案了。代码如下: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
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$时,$[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
19
20
21
22
23
24
25
26
27
28
29
30
31
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 ));
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 ;
else if (c[i-1 ][j] > c[i][j-1 ])
c[i][j] = c[i-1 ][j];
else
c[i][j] = c[i][j-1 ];
}
}
return c[len1][len2];
}
在情况2和情况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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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];
}
这里配合下图更好理解。
这里的根据路径输出的函数为:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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章,动态规划内容。