精品推荐：
《征服数据结构》专栏：50多种数据结构彻底征服
《经典图论算法》专栏：50多种经典图论算法全部掌握
11月5日，字节跳动公司内部发布了年内第四份《企业纪律与职业道德委员会通报》。《通报》显示，103人因违法违规行为被辞退（含外包及实习生），其中11人因涉嫌构成刑事犯罪，被公安机关立案侦查。
上述涉嫌构成刑事犯罪的11人中，从涉嫌罪名来看，其中1人涉嫌职务侵占罪，5人涉嫌非国家工作人员受贿罪，另有5人未透露具体涉嫌罪名。
这份内部通报中，字节跳动还透露了近期备受关注的实习生破坏模型训练事件。
文件指出，在2024年6月至7月期间，一名前实习生田某某因对团队资源分配不满，通过编写和修改代码恶意破坏了团队的模型训练任务，导致了资源的浪费。字节跳动已终止了与该实习生的实习合同。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第64题：最小路径和。
问题描述
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
输入：grid = [[1,2,3],[4,5,6]]
输出：12
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200
动态规划解决
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
for (int i = 1; i < m; i++)// 第一列只能从上面下来
grid[i][0] += grid[i - 1][0];
for (int i = 1; i < n; i++)// 第一行只能从左边过来
grid[0][i] += grid[0][i - 1];
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)// 递推公式
grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
return grid[m - 1][n - 1];
}
public:
int minPathSum(vector<vector<int>> &grid) {
int m = grid.size(), n = grid[0].size();
for (int i = 1; i < m; i++)// 第一列只能从上面下来
grid[i][0] += grid[i - 1][0];
for (int i = 1; i < n; i++)// 第一行只能从左边过来
grid[0][i] += grid[0][i - 1];
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)// 递推公式
grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
return grid[m - 1][n - 1];
}
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
for i in range(1, m): # 第一列只能从上面下来
grid[i][0] += grid[i - 1][0]
for i in range(1, n): # 第一行只能从左边过来
grid[0][i] += grid[0][i - 1]
for i in range(1, m):
for j in range(1, n): # 递推公式
grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
return grid[m - 1][n - 1]
