Leetcode 956. Tallest Billboard

[Woodyiiiiiii]

956. Tallest Billboard

956. Tallest Billboard
Easy Java Solution using HashMap

一开始我想着用状压来表示状态，但发现，这样会出现三种状态表示(一个是steel，第二个是第二个steel，最后是未选上的可以不显示)，接下来一共总状态就有(1 << n) * (1 << n)了，肯定会超时。那我们要继续优化，压缩状态。

这时候可以观察到范围：sum(rods[i]) <= 5000，这让我想起背包了，能不能利用起来呢？再加上题目中心是两个steel之间的长度差值，我们只需要关注差值就行了，也就是说设置状态dfs(i, diff)，状态结束是i >= n时diff会不会等于0，否则返回最小INT。这是子集形DP。这样子总时间复杂度是O(nsum(rods[i]))。

知识点：

1. 以差值作为状态表示。抛弃状压用位的做法
2. 用String作为key
3. 返回值以最小值处理

class Solution {
    int[] rods;
    int n;
    Map<String, Integer> memo = new HashMap<>();

    public int tallestBillboard(int[] rods) {
        this.rods = rods;
        this.n = rods.length;
        return dfs(0, 0);
    }
    
    private int dfs(int i, int diff) {
        if (i == n) {
            return diff == 0 ? 0 : Integer.MIN_VALUE;
        }
        String key = i + "," + diff;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        int res = Math.max(dfs(i + 1, diff), dfs(i + 1, diff + rods[i]));
        res = Math.max(res, rods[i] + dfs(i + 1, diff - rods[i]));
        memo.put(key, res);
        return res;
    }
}

当然可以翻译成递推。