class Solution {
public:
int tallestBillboard(vector<int>& rods) {
}
};
956. 最高的广告牌
你正在安装一个广告牌，并希望它高度最大。这块广告牌将有两个钢制支架，两边各一个。每个钢支架的高度必须相等。
你有一堆可以焊接在一起的钢筋 rods。举个例子，如果钢筋的长度为 1、2 和 3，则可以将它们焊接在一起形成长度为 6 的支架。
返回 广告牌的最大可能安装高度 。如果没法安装广告牌，请返回 0 。
示例 1：
输入：[1,2,3,6]
输出：6
解释：我们有两个不相交的子集 {1,2,3} 和 {6}，它们具有相同的和 sum = 6。
示例 2：
输入：[1,2,3,4,5,6]
输出：10
解释：我们有两个不相交的子集 {2,3,5} 和 {4,6}，它们具有相同的和 sum = 10。
示例 3：
输入：[1,2] 输出：0 解释：没法安装广告牌，所以返回 0。
提示：
0 <= rods.length <= 201 <= rods[i] <= 1000sum(rods[i]) <= 5000原站题解
golang 解法, 执行用时: 248 ms, 内存消耗: 7.2 MB, 提交时间: 2023-09-28 23:38:50
var p map[int]map[int]int
func tallestBillboard(rods []int) int {
p = make(map[int]map[int]int)
for i := 0; i < len(rods); i++ {
p[i] = make(map[int]int)
}
return dp(rods, 0,0)
}
func dp(rods []int, i int, s int) int {
if i == len(rods){
if s == 0{
return 0
}else {
return -1
}
}
if ans ,ok:=p[i][s];ok{
return ans
}
ans :=dp(rods, i+1, s+rods[i])
if ans >=0{
ans+=rods[i]
}
ans = max(ans,dp(rods,i+1,s))
ans = max(ans,dp(rods, i+1,s-rods[i]))
p[i][s] = ans
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
python3 解法, 执行用时: 760 ms, 内存消耗: 29.8 MB, 提交时间: 2023-09-28 23:38:03
# 折半搜索
class Solution:
def tallestBillboard(self, rods: List[int]) -> int:
def make(A: List[int]) -> dict:
states = {(0, 0)}
for x in A:
states |= ({(a+x, b) for a, b in states} |
{(a, b+x) for a, b in states})
delta = {}
for a, b in states:
delta[a-b] = max(delta.get(a-b, 0), a)
return delta
N = len(rods)
Ldelta = make(rods[:N//2])
Rdelta = make(rods[N//2:])
ans = 0
for d in Ldelta:
if -d in Rdelta:
ans = max(ans, Ldelta[d] + Rdelta[-d])
return ans
java 解法, 执行用时: 147 ms, 内存消耗: 52.8 MB, 提交时间: 2023-09-28 23:36:25
import java.awt.Point;
class Solution {
public int tallestBillboard(int[] rods) {
int N = rods.length;
Map<Integer, Integer> Ldelta = make(Arrays.copyOfRange(rods, 0, N/2));
Map<Integer, Integer> Rdelta = make(Arrays.copyOfRange(rods, N/2, N));
int ans = 0;
for (int d: Ldelta.keySet())
if (Rdelta.containsKey(-d))
ans = Math.max(ans, Ldelta.get(d) + Rdelta.get(-d));
return ans;
}
public Map<Integer, Integer> make(int[] A) {
Point[] dp = new Point[60000];
int t = 0;
dp[t++] = new Point(0, 0);
for (int v: A) {
int stop = t;
for (int i = 0; i < stop; ++i) {
Point p = dp[i];
dp[t++] = new Point(p.x + v, p.y);
dp[t++] = new Point(p.x, p.y + v);
}
}
Map<Integer, Integer> ans = new HashMap();
for (int i = 0; i < t; ++i) {
int a = dp[i].x;
int b = dp[i].y;
ans.put(a-b, Math.max(ans.getOrDefault(a-b, 0), a));
}
return ans;
}
}
java 解法, 执行用时: 27 ms, 内存消耗: 47.5 MB, 提交时间: 2023-09-28 23:36:08
class Solution {
int NINF = Integer.MIN_VALUE / 3;
Integer[][] memo;
public int tallestBillboard(int[] rods) {
int N = rods.length;
// "memo[n][x]" will be stored at memo[n][5000+x]
// Using Integer for default value null
memo = new Integer[N][10001];
return (int) dp(rods, 0, 5000);
}
public int dp(int[] rods, int i, int s) {
if (i == rods.length) {
return s == 5000 ? 0 : NINF;
} else if (memo[i][s] != null) {
return memo[i][s];
} else {
int ans = dp(rods, i+1, s);
ans = Math.max(ans, dp(rods, i+1, s-rods[i]));
ans = Math.max(ans, rods[i] + dp(rods, i+1, s+rods[i]));
memo[i][s] = ans;
return ans;
}
}
}
python3 解法, 执行用时: 1104 ms, 内存消耗: 250.2 MB, 提交时间: 2023-09-28 23:35:48
from functools import lru_cache
class Solution:
def tallestBillboard(self, rods: List[int]) -> int:
@lru_cache(None)
def dp(i, s):
if i == len(rods):
return 0 if s == 0 else float('-inf')
return max(dp(i + 1, s),
dp(i + 1, s - rods[i]),
dp(i + 1, s + rods[i]) + rods[i])
return dp(0, 0)
python3 解法, 执行用时: 796 ms, 内存消耗: 17.5 MB, 提交时间: 2023-09-28 23:35:07
# 在原有代码改一点就行了
class Solution:
def tallestBillboard(self, rods):
dp = {0: 0}
for i in rods:
# 浅拷贝和深拷贝请看https://www.cnblogs.com/alimy/p/10374923.html
dp1 = dp.copy()
for k in list(dp1.keys()):
# 把这里的dp1改成了dp，那么获取的就是最新值啦~
dp[k + i] = max(dp.get(k + i, 0), dp1[k] + i)
dp[k - i] = max(dp.get(k - i, 0), dp1[k])
return dp[0]
python3 解法, 执行用时: 736 ms, 内存消耗: 17.6 MB, 提交时间: 2023-09-28 23:34:42
class Solution:
def tallestBillboard(self, rods):
dp = {0: 0}
for i in rods:
for k, b in list(dp.items()):
dp[k + i] = max(dp.get(k + i, 0), b + i)
dp[k - i] = max(dp.get(k - i, 0), b)
return dp[0]