[題目連結](https://leetcode.com/problems/tallest-billboard/description/)

# Method DP(bottom up)
概念說明:
> 第一個想法 dp[x][y],
> x 表示為第一根支架高度,
> y 表示為第二根支架高度
>
很明顯這樣的時間複雜度超時
接下來如何壓縮時間複雜度
可以看出我們並不需要x, y的訊息,
我們只在意 當前高度 與 兩根支架相差多少

> 第二個想法 dp[d] = h1 (h1為較低支架高度, h2為較高支架高度)
> d表示為 兩根支架高度差異
> 可以透過 h1 + d => h2,
> 此時我們可以有兩種做法
> * case 1: rods[i] + h1
> => new_diff = |rods[i] + h1 - h2|
> => dp[new_diff] = min(rods[i] + h1, h2)
>
> * case 2: rods[i] + h2
> => new_diff = |rods[i] + h2 - h1|
> => dp[new_diff] = h1

TC: O(rods.length * sum(rods[i])) SC: O(sum(rods[i]))
完整程式碼

class Solution {
public:
    const int MD = 5000;
    int tallestBillboard(vector<int>& rods) {
        int n = rods.size();
        vector<int> dp(MD + 1, -1);
        dp[0] = 0;

        for(int val : rods) {
            vector<int> next = dp;
            for(int d = 0 ; d <= MD; d++) {
                if(dp[d] < 0) {
                    continue;
                }

                int min_val = dp[d];
                int max_val = d + dp[d];
                
                //add val to min_val
                int nextDiff = abs(min_val + val - max_val);
                next[nextDiff] = max(next[nextDiff], min(min_val + val, max_val));

                //add val to max_val
                nextDiff = max_val + val - min_val;
                if(nextDiff <= MD) {
                    next[nextDiff] = max(next[nextDiff], min_val);
                }
            }
            dp = next;
        }

        return (dp[0] < 0) ? 0 : dp[0];
    }
};