6月17日晚22时，Shopee一名员工收到一份人事部的重要通知，通知称“今天（6月17日）下午，一位Shopee研发中心同事突发身体不适，团队同事和公司于第一时间拨打120急救将该同事送医，但非常悲痛的是，该同事经抢救无效，永远离开了我们。”
6月18日，网传科大讯飞一名员工猝死，早上一名女子躺在科大讯飞合肥总部一楼大厅的玻璃门前，导致众多员工聚集在门外，无法进入公司。拒群聊消息显示，猝死的员工是一名“高级测试（工程师）、38岁”。
我一直强调的是： 挣钱是为了活着，但活着不是为了挣钱 。健康永远是放在第一位的，但有时候拼命工作也是身不由己。
我记得曾经在2014年最多的时候一周工作79个小时，那时候工作是要写日报的，记录每天的工作内容以及上下班时间。不过那时候年轻，如果放到现在肯定是扛不住。
网上有的说应该合理安排工作时间和工作强度，以避免类似事件的再次发生。我觉得这就是个笑话，工作时间和工作强度不是自己安排的，是有人安排的。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第64题：最小路径和。
问题描述
来源：LeetCode第64题
难度：中等
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。
示例2：
输入：grid = [[1,2,3],[4,5,6]] 输出：12
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200
动态规划解决
这题是让找出一条从左上角到右下角的路径，使得路径上的数字总和最小。这是一道典型的动态规划问题。
我们定义 dp[i][j]表示从左上角到位置[i,j]的最小值 ，因为题中说了每次只能向下或向右移动，所以要想到位置[i,j]，可以从上面下来，也可以从左边过来，我们取他的最小值即可，递推公式如下图所示：
对于第一行的每个位置，没法从上面下来，只能从左边过来，同理第一列的每个位置只能从上面下来，所以第一行和第一列要单独处理。
JAVA：
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]; }C++：
public: int minPathSum(vector
> &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]; }
C：
#define min(a, b) (((a) < (b)) ? (a) : (b)) int minPathSum(int **grid, int gridSize, int *gridColSize) { int m = gridSize, n = gridColSize[0]; 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]; }Python：
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]笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。