[956. Tallest Billboard](https://leetcode.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

### 解答
#### Python

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        total = sum(rods)
        dp = [-1] * (total + 1)
        dp[0] = 0

        for rod in rods:
            backup = dp[:]
            for i in range(total - rod + 1):
                if backup[i] < 0:
                    continue
                dp[i + rod] = max(dp[i + rod], backup[i])
                dp[abs(i - rod)] = max(dp[abs(i - rod)], backup[i] + min(i, rod))
        return dp[0]

> 寫得很隨便，沒優化
> [name=Yen-Chi Chen][time=Sat, Jun 24, 2023]

#### C++

class Solution {
public:
    int tallestBillboard(vector<int>& rods) {
        ios_base::sync_with_stdio(0); cin.tie(0);
        int numRods = rods.size();
        int sumRods = accumulate(rods.begin(), rods.end(), 0);
        vector<vector<int>> dp(numRods + 1, vector<int>(sumRods + 1, -1));
        dp[0][0] = 0;
        for (int i = 1; i < numRods + 1; i ++) {
            int currRod = rods[i - 1];
            for (int j = 0; j <= sumRods - currRod; j ++) {
                if (dp[i - 1][j] < 0) {
                    continue;
                }
                dp[i][j] = max(dp[i][j], dp[i - 1][j]);
                dp[i][j + currRod] = max(dp[i][j + currRod], dp[i - 1][j]);
                dp[i][abs(j - currRod)] = max(
                    dp[i][abs(j - currRod)], 
                    dp[i - 1][j] + min(j, currRod));
            }
        }
        return dp[numRods][0];
    }
};

> [name=Jerry Wu][time=24 June, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)