逆天！一不小心把自己上级“开除了”。。

一个朋友前两天发微信说：“我TM居然把我领导‘开除了’！”我当时还以为他开玩笑，直到他甩过来那张OA截图……我整个人都麻了 

原来是公司流程系统出bug也不是，怪就怪在权限太大。

流程全自动飞快推进，审批走完、离职生效、系统注销、工牌失效、邮箱封停，全流程一气呵成。。

你问后果？别问，领导火冒三丈，HR吓得想辞职，我朋友这两天开始研究怎么低调找工作……

只能说，OA系统这波操作，属实给职场整顿上了一课，叫做：权限大，不一定是好事；按钮小，杀伤力却大得离谱。

再牛的打工人，也扛不住手滑一击【备注:文末可领最新资料】

面试题：最高的广告牌

问题是这样的：你有一堆钢筋（数组），每根钢筋有个长度。你要用这些钢筋造两个高度相同的广告牌支架。怎么选这些钢筋能让两个支架的高度尽可能高？

刚看到这题时我内心是拒绝的，脑子里飘过的是"这不就01背包？"但一想，好像又不太一样……两个集合的和必须一样，而且不能重复使用同一根钢筋。更玄的是，它不像常规的“和正好是X”，而是“你随便造，但最终两个高度得一样且尽量高”。

我试了几种暴力方法，果然都超时。于是只好祭出老朋友——动态规划🧠

我先说一下直觉思路，别着急看代码，先想象这样一个状态空间：

我们关注的不是“选了哪些钢筋”，而是“当前两个广告牌之间的高度差是多少”。

这时候，咱们就得搞一个DP表，设 dp[diff] 表示“在当前高度差为 diff 的前提下，我们能构造的较矮那个支架的最大高度”。这里的 diff 是绝对值嘛，不关心左边高还是右边高。

然后遍历每一根钢筋，有三种选择：

1. 不用这根钢筋，状态不变。
2. 把它加到高的那边，高度差变成 diff + h。
3. 把它加到矮的那边，高度差变成 |diff - h|，但注意此时较矮一边的高度会变高。

明白这个逻辑之后，代码其实不复杂了，但有个小技巧：你不能直接在原来的 dp 上修改，不然前后状态会互相影响。得用个 next_dp = dp.copy() 临时副本来保存更新。

贴段代码大家感受下：

deftallestBillboard(rods):
from collections import defaultdict
    dp = {0: 0}  # key是左右高度差，value是矮一边的总高度
for r in rods:
        cur = dp.copy()
for diff, val in cur.items():
# 不选这根钢筋：dp[diff] 保持不变
# 放在高的一边
            dp[diff + r] = max(dp.get(diff + r, 0), val)
# 放在低的一边
            new_diff = abs(diff - r)
            added_val = val + min(diff, r)
            dp[new_diff] = max(dp.get(new_diff, 0), added_val)
return dp[0]

这段代码说实话我第一次看的时候有点懵，尤其是 val + min(diff, r) 这句，我还拿了个例子推了一下才明白：

比如当前差是3，下一根钢筋长度是5，如果你放在矮的那边，差值就成了2，矮的一边也升高了。这时候能增加的高度就是你放这根钢筋后矮边多出来的高度，其实就是 min(diff, r)。

说白了，就是你得保持两边一样高，然后从差值出发，尽量让矮的一边追上来。你要是还不理解这逻辑，建议自己画画图。

那这算法性能怎么样？

时间复杂度其实挺看数据规模的，虽然是 DP，但你想，dp 里面的 key 是差值 diff，最大是所有钢筋长度和的一半，按 LeetCode 的数据来说也就几千。所以就算你有20根钢筋，每根100，DP状态空间也能接受。

我写完之后试了下几个测试样例，跑得还不错：

print(tallestBillboard([1,2,3,6]))  # 输出6
print(tallestBillboard([1,2,3,4,5,6]))  # 输出10
print(tallestBillboard([1,2]))  # 输出0，没法一样高

而且有个事你一定要注意：这个题不能贪心。你比如说把最大的两个放两边，然后再往小的那边补，这是错的。必须全局考虑组合方式，因为可能需要两个小的合起来补大的一边。

还有个变种题，是不是能拆出任意多个对称支架对？也有人试图往多组的方向扩展。说实话那就比这个更复杂了，状态维度一下就上天。

我觉得这个题最大的价值在于：它是动态规划里“差值作为状态维度”的一个经典例子，跟普通的“容量上限”那种背包DP不太一样，更偏“相对差异性”的建模方式。很多人学DP只会套路，比如 dp[i][j] 是“前i个物品、容量j的最大价值”，但是像这种 dp[diff] 的写法，第一次见不太容易上手。