Problem
You are installing a billboard and want it to have the largest height. The billboard will have two steel supports, one on each side. Each steel support must be an equal height.
You have a collection of rods
which can be welded together. For example, if you have rods of lengths 1, 2, and 3, you can weld them together to make a support of length 6.
Return the largest possible height of your billboard installation. If you cannot support the billboard, return 0.
Example 1:
Input: [1,2,3,6] Output: 6 Explanation: We have two disjoint subsets {1,2,3} and {6}, which have the same sum = 6.
Example 2:
Input: [1,2,3,4,5,6] Output: 10 Explanation: We have two disjoint subsets {2,3,5} and {4,6}, which have the same sum = 10.
Example 3:
Input: [1,2] Output: 0 Explanation: The billboard cannot be supported, so we return 0.
Note:
0 <= rods.length <= 20
1 <= rods[i] <= 1000
The sum of rods is at most 5000.
Solution: DP
如果直接暴力搜索的话时间复杂度是O(3^N),铁定超时。对于每一根我们可以选择1、放到左边,2、放到右边,3、不使用。最后再看一下左边和右边是否相同。
题目的数据规模中的这句话非常重要:
The sum of rods is at most 5000.
这句话就是告诉你算法的时间复杂度和sum of rods有关系,通常需要使用DP。
由于每根柱子只能使用一次(让我们想到了 回复 01背包),但是我们怎么去描述放到左边还是放到右边呢?
Naive的方法是用 dp[i] 表示使用前i个柱子能够构成的柱子高度的集合。
e.g. dp[i] = {(h1, h2)}, h1 <= h2
和暴力搜索比起来DP已经对状态进行了压缩,因为我并不需要关心h1, h2是通过哪些(在我之前的)柱子构成了,我只关心它们的当前高度。
然后我可以选择
1、不用第i根柱子
2、放到低的那一堆
3、放到高的那一堆
状态转移的伪代码:
for h1, h2 in dp[i – 1]:
dp[i] += (h1, h2) # not used
dp[i] += (h1, h2 + h) # put on higher
if h1 + h < h2:
dp[i] += (h1 + h, h2) # put on lower
else:
dp[i] += (h2, h1 + h) # put on lower
假设 rods=[1,1,2]
dp[0] = {(0,0)}
dp[1] = {(0,0), (0,1)}
dp[2] = {(0,0), (0,1), (0,2), (1,1)}
dp[3] = {(0,0), (0,1), (0,2), (0,3), (0,4), (1,1), (1,2), (1,3), (2,2)}
但是dp[i]这个集合的大小可能达到sum^2,所以还是会超时…
时间复杂度 O(n*sum^2)
空间复杂度 O(n*sum^2) 可降维至 O(sum^2)
革命尚未成功,同志仍需努力!
all pairs的cost太大,我们还需要继续压缩状态!
重点来了
通过观察发现,若有2个pairs:
(h1, h2), (h3, h4),
h1 <= h2, h3 <= h4, h1 < h3, h2 – h1 = h4 – h3 即 高度差 相同
如果 min(h1, h2) < min(h3, h4) 那么(h1, h2) 不可能产生最优解,直接舍弃。
因为如果后面的柱子可以构成 h4 – h3/h2 – h1 填补高度差,使得两根柱子一样高,那么答案就是 h2 和 h4。但h2 < h4,所以最优解只能来自后者。
举个例子:我有 (1, 3) 和 (2, 4) 两个pairs,它们的高度差都是2,假设我还有一个长度为2的柱子,那么我可以构成(1+2, 3) 以及 (2+2, 4),虽然这两个都是解。但是后者的高度要大于前者,所以前者无法构成最优解,也就没必要存下来。
所以,我们可以把状态压缩到高度差,对于相同的高度差,我只存h1最大的。
我们用 dp[i][j] 来表示使用前i个柱子,高度差为j的情况下最大的公共高度h1是多少。
状态转移(如下图)
dp[i][j] = max(dp[i][j], dp[i – 1][j])
dp[i][j+h] = max(dp[i][j + h], dp[i – 1][j])
dp[i][|j-h|] = max(dp[i][|j-h|], dp[i – 1][j] + min(j, h))
时间复杂度 O(nsum)
空间复杂度 O(nsum) 可降维至 O(sum)
dp[i] := max common height of two piles of height difference i.
e.g. y1 = 5, y2 = 9 => dp[9 – 5] = min(5, 9) => dp[4] = 5.
answer: dp[0]
Time complexity: O(n*Sum)
Space complexity: O(Sum)
C++ hashmap
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua, 172 ms class Solution { public: int tallestBillboard(vector<int>& rods) { unordered_map<int, int> dp; dp[0] = 0; for (int rod : rods) { auto cur = dp; for (const auto& kv : cur) { const int k = kv.first; dp[k + rod] = max(dp[k + rod], cur[k]); dp[abs(k - rod)] = max(dp[abs(k - rod)], cur[k] + min(rod, k)); } } return dp[0]; } }; |
C++ / array
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua, 8 ms class Solution { public: int tallestBillboard(vector<int>& rods) { const int s = accumulate(begin(rods), end(rods), 0); vector<int> dp(s + 1, -1); dp[0] = 0; for (int rod : rods) { vector<int> cur(dp); for (int i = 0; i <= s - rod; ++i) { if (cur[i] < 0) continue; dp[i + rod] = max(dp[i + rod], cur[i]); dp[abs(i - rod)] = max(dp[abs(i - rod)], cur[i] + min(rod, i)); } } return dp[0]; } }; |
C++/2D array
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua, 12 ms class Solution { public: int tallestBillboard(vector<int>& rods) { const int n = rods.size(); const int s = accumulate(begin(rods), end(rods), 0); // dp[i][j] := min(h1, h2), j = abs(h1 - h2) vector<vector<int>> dp(n + 1, vector<int>(s + 1, -1)); dp[0][0] = 0; for (int i = 1; i <= n; ++i) { int h = rods[i - 1]; for (int j = 0; j <= s - h; ++j) { if (dp[i - 1][j] < 0) continue; // not used dp[i][j] = max(dp[i][j], dp[i - 1][j]); // put on the taller one dp[i][j + h] = max(dp[i][j + h], dp[i - 1][j]); // put on the shorter one dp[i][abs(j - h)] = max(dp[i][abs(j - h)], dp[i - 1][j] + min(h, j)); } } return dp[n][0]; } }; |