# 0956. Tallest Billboard
###### tags: `Leetcode` `Hard` `Dynamic Programming` `Knapsack Problem`
Link: https://leetcode.com/problems/tallest-billboard/
## 思路
经典背包思想
以上解法的最大问题是空间和时间的开销都很大，因为left和right都是```[0,5000]```的区间。空间是$o(5000^2)$，时间则是$o(N*5000^2)$。
优化思想
注意```maxDiff```不能通过找所有棍子里面最长的和最短的然后相减算出来 这样遇到```[100,100]```就会错 ```maxDiff```应该是```rods```的sum
还要注意初始化```dp``` array的时候不能用0 0间接说明了left stick长度是0 diff是idx 也就是right stick的长度是-idx 这是不合法的

在for回圈里面 我们要用temp复制dp 因为在同一个i里面我们不能更改dp里面的值 这是因为每次更改我们不仅要往前改 还要往后改(通常是只往前改) 所以遍历到后面的时候会被影响到
## Code

class Solution {
    public int tallestBillboard(int[] rods) {
        int n = rods.length;
        int maxDiff = 5000;
        int[] dp = new int[2*maxDiff+1];
        Arrays.fill(dp, -1);
        dp[maxDiff] = 0;
        for(int i=1; i<=n; i++){
            int[] temp = dp.clone();
            for(int d=-maxDiff; d<=maxDiff; d++){
                if(Math.abs(d+rods[i-1])<=maxDiff && temp[d+rods[i-1]+maxDiff]!=-1) dp[d+maxDiff] = Math.max(dp[d+maxDiff], temp[d+rods[i-1]+maxDiff]);
                if(Math.abs(d-rods[i-1])<=maxDiff && temp[d-rods[i-1]+maxDiff]!=-1) dp[d+maxDiff] = Math.max(dp[d+maxDiff], temp[d-rods[i-1]+maxDiff]+rods[i-1]);
            }
        }
        return dp[maxDiff]==-1?0:dp[maxDiff];
    }
}