中国科学院大学《计算机算法设计与分析》第二次作业

动态规划

国科大(UCAS)卜东波老师算法课作业答案.

1. Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair $(S_i; S_j)$ of elements in this subset satisfies: $S_i \% S_j = 0$ or $S_j \% S_i = 0$.

  • the optimal substructure and DP equation

设 $dp[i]$ 表示最大元素为 $S_i$ 且符合条件的集合中最大集合包含的元素个数

  • pseudo-code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
FindLargestSet(S[1...n], dp[1...n])
max = 1
sort(S[1...n])
for i = 1 -> n do
for j = i - 1 -> 0 do
if S[i] mod S[j] = 0 and dp[i] < dp[j] + 1 then
dp[i] = dp[j] + 1
end if
end for
if max < dp[i] then
max = dp[i]
end if
end for
return max;
  • prove the correctness

设 数组 $S[1…n]$ 中的元素升序排列, $T_j$ 表示 数组 $S[1…j]$ 中满足条件的最大集合,其中最大元素为 $S_j$,则 $S_j$ 可以被 $T_j$ 中所有比它小的元素整数,若 $S_{j+1} ~ \% ~ S_j = 0$,则 $S_{j+1}$ 可以被 $T_j$ 中所有的元素整除,即将 $S_{j+1}$ 加入 $T_j$ 中得到的集合 $T_{j+1}$ 也是符合条件的集合, 得证.

  • the complexity of the algorithm

将 $S[1…n]$ 排序的时间复杂度为 $O(n\log n)$,计算最大集合的时间复杂度为 $O(n^2)$,得

2. Money robbing

A robber is planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

  1. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

  2. What if all houses are arranged in a circle ?

当房子直线排列时

  • the optimal substructure and DP equation

设 $S[1…n]$ 表示 $1…n$ 个房子存有的金额, $dp[i]$ 表示在前 $1…i$ 个房子中能抢到的最大金额

  • pseudo-code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
RobMaxMoney(S[1...n], dp[1...n])
if n = 0 then
return 0
end if
if n = 1 then
return S[1]
end if
res = max(S[1], S[2])
dp[1] = S[1], dp[2] = max(dp[1], S[2])
for i = 2 -> n do
for j = 0 -> i - 2 do
dp[i] = max(dp[i - 1], dp[j] + S[i])
end for
if res < dp[i] then
res = dp[i]
end if
end for
return res;
  • prove the correctness

设当前要抢的为第 $i$ 个房子,如果第 $i - 1$ 个房子已经抢过了,那么第 $i$ 个房子就不能抢了,所以前 $i$ 个房子抢到的最大金额等于前 $i - 1$ 个房子抢到的最大金额,记为 $dp[i] = dp[i - 1]$;如果第 $i - 1$ 个房子没有抢,那么前 $i$ 个房子抢到的最大金额等于前 $j$ 个房子抢到的最大金额加上第 $i$ 个房子抢到的金额,记为 $dp[i] = dp[j] + S[i], ~ j \leq i - 2$,取 $dp[j] + S[i], ~ j \leq i - 2$ 和 $dp[i-1]$ 两者的较大值,即为 $dp[i]$ 的最大值.

  • the complexity of the algorithm

当房子成环排列时

  • the optimal substructure and DP equation

最优子结构的表达式与房子直线排列时的情况相同:

设 $S[1…n]$ 表示 $1…n$ 个房子存有的金额, $dp[i]$ 表示在前 $1…i$ 个房子中能抢到的最大金额

  • pseudo-code
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
RobMaxMoney(S[1...n], dp[1...n], left, right)
if n = 0 then
return 0
end if
if n = 1 then
return S[1]
end if
res = max(S[1], S[2])
dp[1] = S[1], dp[2] = max(dp[1], S[2])
for i = left -> right do
for j = 0 -> i - 2 do
dp[i] = max(dp[i - 1], dp[j] + S[i])
end for
if res < dp[i] then
res = dp[i]
end if
end for
return res;
Main(S[1...n], dp[1...n])
return max(RobMaxMoney(S, dp, 0, n - 1), RobMaxMoney(S, dp, 1, n));
RobMaxMoney(s[0...n-1], cut[0...n-1], isPal[n][n])
for i = 0 -> n-1 do
cut[i] = n - 1 - i
for i = n - 1 -> 0 do
for j = i -> n - 1 do
if s[i] = s[j] and (j - i < 2 or isPal[i + 1][j - 1] = true) then
isPal[i][j] = true
if j = n - 1 then
cut[i] = 0
else
cut[i] = min(cut[i], 1 + cut[j + 1])
end if
end if
end for
end for
return cut[0];
  • prove the correctness

只要将环打破,就可以用房子直线排列时的解法做,打破环的方法就是先假设第 $n$ 个房子不抢,那么能抢的房子范围是 $S[1…n - 1]$,再假设第 $1$ 个房子不抢(因为第 $n$ 个房子和第 $1$ 个房子相邻),那么能抢的房子范围是 $S[2…n]$,这两种情况覆盖的房子范围就是能抢的房子全集 $S[1…n]$,所以取两者的较大值就为所有房子中能抢到的最大金额.

  • the complexity of the algorithm

3. Partition

Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = “aab”, return 1 since the palindrome partitioning [“aa”; “b”] could be produced using 1 cut.

  • the optimal substructure and DP equation

设 字符串 $s$ 长度为 $n$, $s[i]$ 表示字符串 $s$ 的第$i$个字符(下标从0开始),$s[i…j]$ 表示下标从 $i$ 到 $j$ 的子串,$cut[i]$ 表示 $s[i…n-1]$ 最小的分割次数,$isPal[i][j]$ 表示 $s[i…j]$ 是否是回文字符串,是为 $true$,不是为 $false$.

  • pseudo-code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
RobMaxMoney(s[0...n-1], cut[0...n-1], isPal[n][n])
for i = 0 -> n-1 do
cut[i] = n - 1 - i
end for
for i = n - 1 -> 0 do
for j = i -> n - 1 do
if s[i] = s[j] and (j - i < 2 or isPal[i + 1][j - 1] = true) then
isPal[i][j] = true
if j = n - 1 then
cut[i] = 0
else
cut[i] = min(cut[i], 1 + cut[j + 1])
end if
end if
end for
end for
return cut[0]
  • prove the correctness

字符串 $s[i…j]$ 是一个回文字符串,因此在 $s[j]$ 和 $s[j + 1]$ 直接可以切一刀(即分割次数记为1),再加上 $s[j + 1…n-1]$ 的分割次数 $cut[j + 1]$ 即为字符串 $s[i…n-1]$ 分割总次数,取符合 $i <= j < n$ 的所有情况中分割次数最小的作为 $cut[i]$ 的值,字符串 $s[0…n-1]$ 的最小分割次数即为 $cut[0]$.

  • the complexity of the algorithm

6. Maximum profit of transactions

You have an array for which the i-th element is the price of a given stock on day i.

Design an algorithm and implement it to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the
stock before you buy again).

C++代码如下

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
// profits[i][j] 表示第i次交易时,0到j天可以获得的最大收益
// profits[0][j] = 0,因为0次交易时必然没有收益
// profits[i][0] = 0,因为只有1天的股票价格时,不能进行一次完整的交易(买和卖),收益为0
// profits[i][j] = max(profits[i][j - 1], prices[j] - profits[jj] + profits[i - 1][jj])
// = max(profits[i][j - 1], prices[j] + max(profits[i - 1][jj] - profits[jj])), jj < j and j >= 1
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() < 2)
return 0;
int maxProf = 0; // 最大收益
int K = 2; // K表示最多可交易的次数
vector<vector<int>> profits(K + 1, vector<int>(prices.size(), 0));
for (int i = 1; i <= K; i++) {
int tmpMax = profits[i - 1][0] - prices[0];
for (int j = 1; j < prices.size(); j++) {
profits[i][j] = max(profits[i][j - 1], prices[j] + tmpMax);
tmpMax = max(tmpMax, profits[i - 1][j] - prices[j]);
maxProf = max(profits[i][j], maxProf);
}
}
return maxProf;
}
};

版权声明

作者:萝卜姓胡
许可协议:Creative Commons Attribution-ShareAlike 4.0 International License
本文永久链接:http://hw2007.com/2018/10/04/中国科学院大学《计算机算法设计与分析》第二次作业/