Leetcode 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 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

Problem Analysis:

As we can see the constraints sum(rods[i]) ≤ 5000, the sum is not big. So we can use dynamic programming to solve this problem.

We use an array dp, assume dp[i] means we get some rods and get maximum pair of height sum that i is the difference of heights.

We iterate the rods, when we add rods[i], there are two methods: we add rods[i] to the higher part, so we get dp[x + rods[i]] = max(dp[x + rods[i]], dp[x]). Or we add rods[i] to the lower part, we get dp[x-rods[i]] = max(dp[x-rods[i]], dp[x] + rods[i]).

After iterate all rods, the dp[0] is the answer.

Solution

class Solution {
public:
    int tallestBillboard(vector<int>& rods) {
        int sum = accumulate(begin(rods), end(rods), 0);
        vector<int> dp(sum + 1, -1);
        dp[0] = 0;
        for (const auto& item : rods) {
            vector<int> current(dp);
            for (int i = 0; i <= sum - item; ++i) {
                if (current[i] < 0) continue;
                dp[i + item] = max(dp[i + item], current[i]);
                dp[abs(i - item)] = max(dp[abs(i - item)], current[i] + min(i, item));
            }
        }

        return dp[0];
    }
};

Time complexity is O(sum * rods.length)

Space complexity is O(sum)