说实话，这事我看到第一反应就是：不对劲。
他领导问“年终奖还要吗”，这话听着像关心，其实十有八九是在试探。要是真心想发，早就结清了，哪还会回头发微信问一句？
年终奖这种东西，在很多公司根本没保障，特别是民企，写合同的都留一手。你干了几个月，按理说是该有比例发放，但实际操作？呵呵，谁拳头硬谁说了算。
所以这个同学要是我，我就回：“如果公司安排，我当然愿意。”别说死，也别太软。太硬了可能把钱整没，太软了又容易被PUA。
一句话，要钱可以，但得有技巧。打工人不是不能争取利益，但得知道怎么拿，不然就容易被当猴耍
算法题： 最后一块石头的重量 II
这个题乍一看像是“石头剪刀布”的变种，其实背后藏着一个典型的“子集和问题”。什么意思呢？你先别急，我们慢慢来聊。
LeetCode上这道“最后一块石头的重量 II”，我第一次刷的时候就直觉告诉我，这玩意儿跟动态规划有一腿，毕竟啥时候说到“选择两个、求最小”，99%都绕不开背包问题。
但刚开始我还是走了弯路。
我当时想着是不是每次模拟那种“碰撞”操作，反复选两块石头模拟粉碎...结果不用说，这个做法直接超时了。而且模拟到后期你会发现，情况组合太多，根本控制不住。
所以这题的核心其实是——你要把石头分成两堆，让它们重量尽量接近。为什么？因为每次碰撞最终都会变成两个子集合的差值。
比如说你把石头分成两个子集 A 和 B，分别加总后为 sumA 和 sumB，那么最终剩下的重量其实就是 |sumA - sumB|，也就是它们重量的差。
这个时候你是不是想起来一个经典的背包模型了？
对，就是0-1背包，我们目标是把石头分成两个重量尽量接近的子集，说人话就是尽可能让其中一个子集的和接近总重量的一半。
我们把所有石头的总重量记为 sum，那我们的目标就是在这些石头里选出一些石头，使得它们的总和不超过 sum / 2 并且尽可能大。为啥不超过 sum / 2？因为这样剩下的另一半也不可能比这个更小，从而差值最小。
所以，动态规划就来了！
我们定义一个布尔数组 dp[j] 表示是否可以用这些石头凑出重量 j，初始条件是 dp[0] = true，表示啥也不选就是 0 重量。然后我们遍历每一块石头，不断更新这个 dp 数组，从大往小更新，防止重复使用。
代码长这样：
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for (int stone : stones) {
sum += stone;
}
int target = sum / 2;
boolean[] dp = newboolean[target + 1];
dp[0] = true;
for (int stone : stones) {
for (int j = target; j >= stone; j--) {
dp[j] = dp[j] || dp[j - stone];
}
}
for (int i = target; i >= 0; i--) {
if (dp[i]) {
return sum - 2 * i;
}
}
return0;
}
整个流程其实蛮“背包”的——对于每一块石头来说，你都可以选择“装”进你的背包（子集）或者不装，最后我们找出最大能装到 sum / 2 的重量 i，结果就是 sum - 2 * i。
有时候大家会问，这种题能不能用 DFS + 剪枝去暴力跑一遍？理论上行，但实践中复杂度是指数级别的，很容易TLE，除非题目特别小。
我还试过用记忆化搜索模拟这种“分组差值”的思路，但代码复杂度高，且debug不如DP稳定。所以我个人在遇到这种类似“子集和接近目标”的问题时，第一反应都是往动态规划靠。
当然这题也不是没有变种空间。比如如果石头重量改成可以是负数怎么办？这个问题就变味了，需要考虑更多边界问题。或者换个问法，如果要求不能完全粉碎，每次只能削减一半重量呢？那就得重新设计状态转移，甚至不是0-1背包能搞定的了。
最后要提醒一点，这题虽然看起来像动规模板题，但关键点在于你能不能从“碰撞过程”联想到“子集和问题”。一旦你能转化这个思路，这类题几乎都可以用类似的背包套路去搞定。
这类题我建议大家要多刷几次，把“如何把现实问题建模成背包”这个思路练出来，比死记硬背DP表结构强太多了。
-END -