956. 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 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:

  1. 0 <= rods.length <= 20
  2. 1 <= rods[i] <= 1000
  3. The sum of rods is at most 5000.

这道题说是要装个很高的广告牌,有很多长度不同的支撑杆,多个支撑杆可以粘合成一个更长的,广告牌需要两个长度相等的支撑杆,问广告牌最高能放多高。去掉这个具体的场景,其实这道题讨论的就是在数组中选取若干个数字分成和相同的两组,问这个最大和是多少。跟之前那道 Partition Equal Subset Sum 非常的类似,不过那道题是要用到所有的数字,所以一旦可以分割的话,那么最大和就是固定的,为数组所有数字之和的一半。而这道题不强制要用所有的数字,所以最大和是不确定的。所以之前那道题的方法在这里完全不适用,但也不是完全没有关系,起码动态规划 Dynamic Programming 的思想还是要用的。博主强调过很多次,像这种数组啊,字符串啊之类的极值问题,DP 解法十有八九绕不开,若还是个 Hard 题,那么基本就是 DP 无疑了。这道题的一大难点就是 dp 不容易定义,即便你知道要用 DP,是否能写出正确的定义式也是个问题。下面这种解法参考了 zxybazh 大神的帖子,这里我们定一个一个二维 dp 数组,其中 dp[i][j] 表示从前i个数字中选出数字组成两组(组0和组1,这里假设组0数字之和一定小于组1),此时的二者中的较大长度,其实也就是组1的数字之和,并且j表示二组数字之和的差值。接下来就是要找出状态转移方程,如何从之前的状态推导出 dp[i][j]。当把 rod[i] 加入其中的一组时,此时有三种情况:

  • 将 rod[i] 加入组1时,由于组1的数字和大,所以增加新数字会拉大两组原本的差值,若加入之后的差值为j,则加入之前则为 j-rods[i],所以可以用 dp[i-1][j-rods[i]] + rods[i] 来更新 dp[i][j]。

  • 将将 rod[i] 加入组0时,且加入之后组0的数字之和仍小于组1,但此时二者的差距变小了,若加入之后的差值为j,则加入之前则为 j+rods[i],所以可以用 dp[i-1][j+rods[i]] 来更新 dp[i][j]。

  • 将将 rod[i] 加入组0时,且加入之后组0的数字之和超过了组1,说明这个新数字要大于原本两个组之间的差值,若加入之后的差值为j,则加入之前则为 rods[i]-j,所以可以用 dp[i-1][rods[i]-j] + j 来更新 dp[i][j]。

搞清楚了这三种情况,就可以写出代码了,最终的结果是存在 dp[n][0] 中的,因为这表示从前n个数字中选出数字组成两组,且两组之和差为0,说明可以组成相同和的两组,参见代码如下:

解法一:

class Solution {
public:
    int tallestBillboard(vector<int>& rods) {
        int n = rods.size();
        vector<vector<int>> dp(n + 1, vector<int>(5001));
        for (int i = 0; i <= 5000; i++) dp[0][i] = -1e9;
        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= 5000; ++j) {
                dp[i][j] = dp[i - 1][j];
                if (j >= rods[i - 1]) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - rods[i - 1]] + rods[i - 1]);
                } else {
                    dp[i][j] = max(dp[i][j], dp[i - 1][rods[i - 1] - j] + j);
                }
                if (j + rods[i - 1] <= 5000) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j + rods[i - 1]]);
                }
            }
        }
        return dp[n][0];
    }
};

再来看一种空间复杂度更小的解法,这里就照着 lee215 大神的帖子 来讲解吧。定义了一个一维数组 dp,其中 dp[i] 表示两组中较小的那组的数字之和,且i表示两组的数字和的差值。其中 dp[0] 要初始化为0。现在假设有两组数字,其和的差值为d,如下所示:

-—— y ——|—– d —–|

-—— y ——|

现在要加入一个新的数字x的话,还是有三种情况:

  • 加入到长的那组,使得长的更长,此时要用 y 来更新 dp[d+x],如下所示:

-—— y ——|—– d —–|—– x —–|

-—— y ——|

  • 加入到短的那组,加了之后还是没有超过长的组,此时要用 y+x 来更新 dp[d-x],如下所示:

-——y——|—– d —–|

-——y——|— x —|

  • 加入到短的那组,加了之后超过了长的组,此时要用 y+d 来更新 dp[x-d],如下所示:

-—— y ——|—– d —–|

-—— y ——|——- x ——-|

可以发现,后两种情况可以合成为一种,dp[abs(x - d)] = max(dp[abs(x - d)], y + min(d, x)),最终的结果保存在 dp[0] 中,参见代码如下:

解法二:

class Solution {
public:
    int tallestBillboard(vector<int>& rods) {
        vector<int> dp(5001, -1e9);
        dp[0] = 0;
        for (int x : rods) {
            vector<int> cur = dp;
            for (int d = 0; d + x <= 5000; ++d) {
                dp[d + x] = max(dp[d + x], cur[d]);
                dp[abs(d - x)] = max(dp[abs(d - x)], cur[d] + min(d, x));
            }
        }
        return dp[0];
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/956

类似题目:

Partition Equal Subset Sum

参考资料:

https://leetcode.com/problems/tallest-billboard/

https://leetcode.com/problems/tallest-billboard/discuss/203274/Simple-C%2B%2B-DP-beating-100-O(NM)

https://leetcode.com/problems/tallest-billboard/discuss/203181/JavaC%2B%2BPython-DP-min(O(SN2)-O(3N2-*-N)

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation