还有后续?!
我实在是没想到，字节大模型投毒这事儿，还能有后续 🤣🤣🤣
10-20，我们梳理了 字节大模型被实习生投毒的事件 这事儿，当时的主要结论是：确有此事儿，但被投毒的只是研究类的训练任务，不涉及商用大模型和线上业务，网上说的「涉及 8000 多张卡，造成上千万美元损失」都是夸大说法。
11-28，我们更新了后续：字节决定起诉该实习生，请求法院，判令该实习生赔偿公司侵权损失 800 万元及合理支出 2 万元，并公开赔礼道歉。
并且当时有说法是，字节之所以追究该实习生，是因为实习生对于投毒这事儿拒不承认，把锅甩给了其他实习生。
而今天（12-04），最新的瓜又来了。
这位实习生在字节商业化技术部门实习期间与团队合作发表的论文，以 NeurIPS 2024 第六高分（7,8,8,8）的成绩，获得了 NeurIPS 2024 最佳论文。
虽然 NeurIPS 2024 的正式开奖时间还没到（于 12月9日~12月15日 在温哥华召开），但是一些大会的注册者，已经可以在网站上看到具体的评分成绩，海外网友也是提前给出了相应的爆料：
若消息无误，这位实习生的这篇论文，将会成为国内第二篇 NeurIPS Best Paper！！！
目前来看，消息可靠性还是很高的。
一方面是主要消息来源都是海外（一手信息），另一方面，该实习生此前就已经有多篇顶会论文，且被引用多次：
目前来看，这位同学不是一般的强，是强得离谱。
这样级别的天才少年，正常年薪过百万不在话下，没准字节这 800W，他还真的赔得起 🤣🤣🤣
但怎么说呢，人品比什么都重要，否则再好的技术都只能造出更大的恶果。
对此，你怎么看？你觉得这位实习生的后续前程如何？
是会被大公司抢着"不拘一格"地招入麾下，还是说真的如字节所愿（向行业联盟举报该实习生），职业生涯走到头了？
如果实在要我猜一个的话，可能是前者吧。
毕竟这个世界对强者的宽容程度，超乎想象
...
回归主题。
来一道和「字节跳动」相关的算法题。
题目描述
平台：LeetCode
题号：1473
在一个小城市里，有 m 个房子排成一排，你需要给每个房子涂上 n 种颜色之一（颜色编号为 1 到 n ）。
有的房子去年夏天已经涂过颜色了，所以这些房子不可以被重新涂色。
我们将连续相同颜色尽可能多的房子称为一个街区。
（比方说 houses = [1,2,2,3,3,2,1,1]，它包含 5 个街区 [{1}, {2,2}, {3,3}, {2}, {1,1}] 。）
给你一个数组 houses，一个 m * n 的矩阵 cost 和一个整数 target，其中：
houses[i]：是第i个房子的颜色，0表示这个房子还没有被涂色。cost[i][j]：是将第i个房子涂成颜色j + 1的花费。
请你返回房子涂色方案的最小总花费，使得每个房子都被涂色后，恰好组成 target 个街区。
如果没有可用的涂色方案，请返回 -1。
示例 1：
输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出：9
解释：房子涂色方案为 [1,2,2,1,1]
此方案包含 target = 3 个街区，分别是 [{1}, {2,2}, {1,1}]。
涂色的总花费为 (1 + 1 + 1 + 1 + 5) = 9。
示例 2：
输入：houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出：11
解释：有的房子已经被涂色了，在此基础上涂色方案为 [2,2,1,2,2]
此方案包含 target = 3 个街区，分别是 [{2,2}, {1}, {2,2}]。
给第一个和最后一个房子涂色的花费为 (10 + 1) = 11。
示例 3：
输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
输出：5
示例 4：
输入：houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
输出：-1
解释：房子已经被涂色并组成了 4 个街区，分别是 [{3},{1},{2},{3}] ，无法形成 target = 3 个街区。
提示：
动态规划
定义 为考虑前 间房子，且第 间房子的颜色编号为 ，前 间房子形成的分区数量为 的所有方案中的「最小上色成本」。
我们不失一般性的考虑 该如何转移，由于某些房子本身就已经上色，上色的房子是不允许被粉刷的。
我们可以根据第 间房子是否已经被上色，进行分情况讨论：
第 间房子已经被上色，即 ，此时只有满足 的状态才是有意义的，其余状态均为 INF。 同时根据「第 间房子的颜色 」与「第 间房子的颜色 」是否相同，会决定第 间房子是否形成一个新的分区。这同样需要进行分情况讨论。 整理后的转移方程为：
第 间房子尚未被上色，即 ，此时房子可以被粉刷成任意颜色。不会有无效状态的情况。 同样，根据「第 间房子的颜色 」与「第 间房子的颜色 」是否相同，会决定第 间房子是否形成一个新的分区。 转移方程为：
一些编码细节：
下标转换：这是个人习惯，无论做什么题，我都喜欢将下标转换为从 开始，目的是为了「节省负值下标的分情况讨论」、「将无效状态限制在 下标内」或者「充当哨兵」等等。 将 0x3f3f3f3f作为INF：因为目标是求最小值，我们应当使用一个较大值充当正无穷，来关联无效状态。同时为了确保不会出现「在正无穷基础上累加导致丢失正无穷含义」的歧义情况，我们可以使用一个有「累加空间」的值作为「正无穷」（这个问题刚好最近在 这里 专门讲过）。
Java 代码：
class Solution {
int INF = 0x3f3f3f3f;
public int minCost(int[] hs, int[][] cost, int m, int n, int t) {
int[][][] f = new int[m + 1][n + 1][t + 1];
// 不存在分区数量为 0 的状态
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
f[i][j][0] = INF;
}
}
for (int i = 1; i <= m; i++) {
int color = hs[i - 1];
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= t; k++) {
// 形成分区数量大于房子数量，状态无效
if (k > i) {
f[i][j][k] = INF;
continue;
}
// 第 i 间房间已经上色
if (color != 0) {
if (j == color) { // 只有与「本来的颜色」相同的状态才允许被转移
int tmp = INF;
// 先从所有「第 i 间房形成新分区」方案中选最优（即与上一房间颜色不同）
for (int p = 1; p <= n; p++) {
if (p != j) {
tmp = Math.min(tmp, f[i - 1][p][k - 1]);
}
}
// 再结合「第 i 间房不形成新分区」方案中选最优（即与上一房间颜色相同）
f[i][j][k] = Math.min(f[i - 1][j][k], tmp);
} else { // 其余状态无效
f[i][j][k] = INF;
}
// 第 i 间房间尚未上色
} else {
int u = cost[i - 1][j - 1];
int tmp = INF;
// 先从所有「第 i 间房形成新分区」方案中选最优（即与上一房间颜色不同）
for (int p = 1; p <= n; p++) {
if (p != j) {
tmp = Math.min(tmp, f[i - 1][p][k - 1]);
}
}
// 再结合「第 i 间房不形成新分区」方案中选最优（即与上一房间颜色相同）
// 并将「上色成本」添加进去
f[i][j][k] = Math.min(tmp, f[i - 1][j][k]) + u;
}
}
}
}
// 从「考虑所有房间，并且形成分区数量为 t」的所有方案中找答案
int ans = INF;
for (int i = 1; i <= n; i++) {
ans = Math.min(ans, f[m][i][t]);
}
return ans == INF ? -1 : ans;
}
}
C++ 代码：
class Solution {
public:
const int INF = 0x3f3f3f3f;
int minCost(vector<int>& hs, vector<vector<int>>& cost, int m, int n, int t) {
vector<vector<vector<int>>> f(m + 1, vector<vector<int>>(n + 1, vector<int>(t + 1, 0)));
// 不存在分区数量为 0 的状态
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
f[i][j][0] = INF;
}
}
for (int i = 1; i <= m; i++) {
int color = hs[i - 1];
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= t; k++) {
// 形成分区数量大于房子数量，状态无效
if (k > i) {
f[i][j][k] = INF;
continue;
}
// 第 i 间房间已经上色
if (color != 0) {
if (j == color) { // 只有与「本来的颜色」相同的状态才允许被转移
int tmp = INF;
// 先从所有「第 i 间房形成新分区」方案中选最优（即与上一房间颜色不同）
for (int p = 1; p <= n; p++) {
if (p != j) {
tmp = min(tmp, f[i - 1][p][k - 1]);
}
}
// 再结合「第 i 间房不形成新分区」方案中选最优（即与上一房间颜色相同）
f[i][j][k] = min(f[i - 1][j][k], tmp);
} else { // 其余状态无效
f[i][j][k] = INF;
}
// 第 i 间房间尚未上色
} else {
int u = cost[i - 1][j - 1];
int tmp = INF;
// 先从所有「第 i 间房形成新分区」方案中选最优（即与上一房间颜色不同）
for (int p = 1; p <= n; p++) {
if (p != j) {
tmp = min(tmp, f[i - 1][p][k - 1]);
}
}
// 再结合「第 i 间房不形成新分区」方案中选最优（即与上一房间颜色相同）
// 并将「上色成本」添加进去
f[i][j][k] = min(tmp, f[i - 1][j][k]) + u;
}
}
}
}
// 从「考虑所有房间，并且形成分区数量为 t」的所有方案中找答案
int ans = INF;
for (int i = 1; i <= n; i++) {
ans = min(ans, f[m][i][t]);
}
return ans == INF ? -1 : ans;
}
};
时间复杂度：共有 个状态需要被转移，每次转移需要枚举「所依赖的状态」的颜色，复杂度为 。整体复杂度为 空间复杂度：
状态定义的由来
对于有一定 DP 刷题量的同学来说，上述的「状态定义」应该很好理解。
根据经验，我们可以很容易确定「房间编号维度 」和「分区数量维度 」需要纳入考虑，同时为了在转移过程中，我们能够清楚知道从哪些状态转移过来需要增加「分区数量」，哪些状态转移过来不需要增加，因此需要多引入「最后一间房间颜色 」维度。
至于对 DP 不熟悉的同学，可以从写「爆搜」开始入手。
这里的“写”不一定真的要动手去实现一个完整的「爆搜」方案，只需要合理设计出来 DFS 函数签名即可。
但为了更好理解，我写了一个完整版的供你参考。
Java 代码：
class Solution {
int INF = 0x3f3f3f3f;
int ans = INF;
int[] hs;
int[][] cost;
int m, n, t;
public int minCost(int[] _hs, int[][] _cost, int _m, int _n, int _t) {
m = _m; n = _n; t = _t;
hs = _hs;
cost = _cost;
dfs(0, -1, 0, 0);
return ans == INF ? -1 : ans;
}
// u : 当前处理到的房间编号
// last : 当前处理的房间颜色
// cnt : 当前形成的分区数量
// sum : 当前的上色成本
void dfs(int u, int last, int cnt, int sum) {
if (sum >= ans || cnt > t) return;
if (u == m) {
if (cnt == t) {
ans = Math.min(ans, sum);
}
return;
}
int color = hs[u];
if (color == 0) {
for (int i = 1; i <= n; i++) {
int nCnt = u - 1 < 0 ? 1 : last == i ? cnt : cnt + 1;
dfs(u + 1, i, nCnt, sum + cost[u][i - 1]);
}
} else {
int nCnt = u - 1 < 0 ? 1 : last == color ? cnt : cnt + 1;
dfs(u + 1, color, nCnt, sum);
}
}
}
时间复杂度： n为颜色数量，m为房间数量。不考虑剪枝效果，每个房间都可以粉刷n种颜色，复杂度为指数级别的空间复杂度：忽略递归带来的额外空间开销。复杂度为
可以发现，DFS 的可变参数有四个，其中 sum 是用于更新最终答案 ans 的，其应该作为动规值，其余三个参数，作为动规数组的三个维度。
至此，我们可以确定动态规划的「状态定义」，关于如何利用这种「技巧」来得到一个可靠的「状态定义」最早在 这里 讲过。
记忆化搜索
看到评论区有同学贴了「记忆化搜索」的版本，那么就作为补充增加到题解吧 ~
注意记忆化容器应当与我们的「动规数组」结构保存一致。
Java 代码：
class Solution {
int INF = 0x3f3f3f3f;
int m, n, t;
int[] hs;
int[][] cost;
boolean[][][] vis;
int[][][] cache;
public int minCost(int[] _hs, int[][] _cost, int _m, int _n, int _t) {
m = _m; n = _n; t = _t;
hs = _hs;
cost = _cost;
vis = new boolean[m + 1][n + 1][t + 1];
cache = new int[m + 1][n + 1][t + 1];
int ans = dfs(0, 0, 0, 0);
return ans == INF ? -1 : ans;
}
int dfs(int u, int last, int cnt, int sum){
if(cnt > t) return INF;
if(vis[u][last][cnt]) return cache[u][last][cnt];
if (u == m) return cnt == t ? 0 : INF;
int ans = INF;
int color = hs[u];
if(color == 0){
for(int i = 1; i <= n; i++){
int nCnt = u == 0 ? 1 : last == i ? cnt : cnt + 1;
int cur = dfs(u + 1, i, nCnt, sum + cost[u][i - 1]);
ans = Math.min(ans, cur + cost[u][i - 1]);
}
} else{
int nCnt = u == 0 ? 1 : last == color ? cnt : cnt + 1;
int cur = dfs(u + 1, color, nCnt, sum);
ans = Math.min(ans, cur);
}
vis[u][last][cnt] = true;
cache[u][last][cnt] = ans;
return ans;
}
}
时间复杂度：共有 个状态需要被转移，每次转移需要枚举「所依赖的状态」的颜色，复杂度为 。整体复杂度为 空间复杂度：
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
