35页PPT被嫌不用心，原来转正考核根本不是看内容，而是变相考察你愿不愿意“卷命”

“兄弟，你要不要建个广告牌？”

第一次刷到这道题的时候，我还以为是要做什么 Web 项目，结果一看题目，我人都傻了：你给我一堆钢材（用数组表示长度），要我凑出两块高度相等的广告牌，还能扔掉不要的钢材，问这两块广告牌最高能多高？

说人话就是：从数组里选出两组子集，它们的和要一样，而且这个和要尽可能大。听起来像不像在玩那种"搬砖对称叠高塔"的小游戏？一不小心左边高了，右边矮了，老板还得过来给你评价一下：结构不稳，重做。

我一开始想的很暴力，双重回溯套个 DFS：每块钢材三种状态——给左边、给右边、不要。然后硬暴力试出最大高度。但这玩意儿复杂度是 3^n，数组长度一大就直接升天，面试官不挂你挂谁。

后来我冷静下来一想，这不就是 “子集和差为 0 的最大和问题” 嘛，经典的 动态规划题。于是我用了一个套路比较少见但是特别优雅的 DP 解法。

核心思想是这样的：

我们设 dp[diff] = sum 表示：左右两个子集的差值为 diff 时，较矮的那一边最大能有多高的总和。

然后我们用一张 HashMap<Integer, Integer> 来模拟这个过程：

publicint tallestBillboard(int[] rods) {
    Map<Integer, Integer> dp = newHashMap<>();
    dp.put(0, 0);

for (int rod : rods) {
        Map<Integer, Integer> cur = newHashMap<>(dp);
for (int diff : cur.keySet()) {
inttaller = cur.get(diff);
intshorter = taller - diff;

// 1. 不使用这个 rod，什么都不变

// 2. 把 rod 加到较高的那一边
intnewDiff1 = diff + rod;
intnewHeight1 = taller;
            dp.put(newDiff1, Math.max(dp.getOrDefault(newDiff1, 0), newHeight1));

// 3. 把 rod 加到较矮的那一边
int newShorter = shorter + rod;
int newDiff2 = Math.abs(newShorter - taller);
int newHeight2 = Math.max(newShorter, taller);
            dp.put(newDiff2, Math.max(dp.getOrDefault(newDiff2, 0), Math.min(newShorter, taller)));
        }
    }

return dp.getOrDefault(0, 0);
}

我第一次写出来这个的时候，直接在 IDE 前大喊一句“啊哈！动态规划你逃不过我法眼！”

而且你仔细看这个过程，它本质上和我们在工作里做需求选型差不多。有时我们选左边的技术栈，比如 Spring Boot，有时我们觉得右边的更香，比如 Quarkus，有时我们什么都不选，摆烂一下。最终能凑出一样高的方案，那就说明方案平衡、有性价比，还能交差。

还有一点特别程序员味儿的细节就是：用 HashMap 替代数组来存 DP 状态，避免了负数索引的问题，尤其是那种“差值”的 DP，一不注意下标就炸掉。用 Map 就灵活多了，状态空间也会更小点。

当然，这题也有更简洁点的版本，如果你脑回路特别清奇，可以把这个题看成是“等和划分问题”的变种，用背包去解。但我觉得用这个“差值 DP”才是最 elegant 的解法，面试时能让对面眼前一亮：这小子，会点东西！

写完这题，我忽然意识到程序员工作里其实有很多“差值 DP”的场景——比如需求总是不对称、业务总是左右不平衡、领导总觉得你还有富余资源。我们要做的，不就是如何让自己的“两边”尽量对齐，然后尽可能高效利用资源？

现实中的广告牌都立在马路边，我们这些程序员的“广告牌”，可能就是简历、项目、博客、开源贡献，而这些，正是我们手里的钢材。怎么切、怎么拼、怎么用，决定了我们最后能立起多高的“人生广告牌”。

而我嘛，现在就想问一句：谁有多余的钢材？我准备换块更大的牌子，写上“内推码了解一下～”