956-最高的广告牌(Tallest Billboard)

原文链接: https://leetcode-cn.com/problems/tallest-billboard

英文原文

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 are given a collection of rods that 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: rods = [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: rods = [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: rods = [1,2]
Output: 0
Explanation: The billboard cannot be supported, so we return 0.

Constraints:

1 <= rods.length <= 20
1 <= rods[i] <= 1000
sum(rods[i]) <= 5000

中文题目

你正在安装一个广告牌，并希望它高度最大。这块广告牌将有两个钢制支架，两边各一个。每个钢支架的高度必须相等。

你有一堆可以焊接在一起的钢筋 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 <= 20
1 <= rods[i] <= 1000
钢筋的长度总和最多为 5000

通过代码

官方题解

方法 1：动态规划

想法

对于每一根钢筋 x，我们会写下 +x，-x 或者 0。我们的目标是最终得到结果 0 并让正数之和最大。我们记所有写下的正数之和为 score。例如，+1 +2 +3 -6 的 score 为 6。

因为 sum(rods) 的大小限制，就说明可以利用这个性质。事实上，如果之前已经写下了一些数字，那么就不需要考虑这些数字是如何得到的。例如，rods = [1, 2, 2, 3]，我们可以用 3 种方法得到和为 3，但只考虑最终的 score 为 3。数字之和的上界是 10001，因为只有 [-5000, 5000] 区间内的整数是可能的值。

算法

dp[i][s] 表示当我们可以使用 rods[j] (j >= i) 时能得到的最大 score，由于之前写下的数字和为 s（不统计在 score 内）。例如，rods = [1, 2, 3, 6]，可以有 dp[1][1] = 5，在写下 1 之后，可以写下 +2 +3 -6 使得剩下的 rods[i:] 获得 score 为 5。

边界情况：dp[rods.length][s] 是 0 当 s == 0，剩余情况为 -infinity 。递推式为 dp[i][s] = max(dp[i+1][s], dp[i+1][s-rods[i]], rods[i] + dp[i+1][s+rods[i]])。

[]
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;
        }
    }
}

[]
from functools import lru_cache
class Solution:
    def tallestBillboard(self, rods):
        @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)

复杂度分析

时间复杂度：$O(NS)$，其中 $N$ 是 rods 的长度，$S$ 是 $\sum \text{rods}[i]$。
空间复杂度：$O(NS)$。

方法 2：折半搜索

想法

暴力搜索的复杂度可以用“折半搜索”优化。在这个问题中，我们有 $3^N$ 种可行方案，对于每个钢筋 x 可以考虑 +x，-x，或者 0 ，我们要让暴力的速度更快。

我们可以让前 $3^{N/2}$ 和后一半分开来考虑，然后再合并他们。例如，如果有钢筋 [1, 3, 5, 7]，那么前两根钢筋可以构成九种状态：[0+0, 0+3, 0-3, 1+0, 1+3, 1-3, -1+0, -1+3, -1-3]，后两根钢筋也可以构成九种状态。

我们对每个状态记录正数之和，以及负数绝对值之和。例如，+1 +2 -3 -4 记为 (3, 7)。同时记状态的 delta 为两者之差 3-7，所以这个状态的 delta 为 -4。

我们的目标是将两个状态合并，使得 delta 之和为 0。score 是所有正数之和，我们希望获得最高的 score。对于每个 delta 我们只会记录具有最高 score 的状态。

算法

将钢筋分成左右两半：左侧和右侧。

对于每一半，暴力计算可达的所有状态，如上定义。然后针对所有状态，记录下 delta 和最大的 score。

然后我们有左右两半的 [(delta, score)] 信息。我们找到 delta 为 0 时最大的 score 和。

[]
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;
    }
}

[]
class Solution(object):
    def tallestBillboard(self, rods):
        def make(A):
            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

复杂度分析

时间复杂度：$O(3^{N/2})$，其中 $N$ 是 rods 的长度。
空间复杂度：$O(3^{N/2})$。

统计信息

通过次数	提交次数	AC比率
4210	9562	44.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途