大家好，我是程序员小灰。
今天在朋友圈看到一张图片：某大厂开始“捡漏”35+的人员了。
好家伙，如果是真的，那程序员可就越老越吃香了，按道理，从古至今，技术活本来就应该是这样的待遇，学的越久、懂得越多、接触的越多，应该是能更加游刃有余的处理好本质工作，而不应该像现在这样，从 20 岁出头开始工作，每年都要几乎从头开始学一门新的技术、新的框架、新语言，结果到 35 岁时发现一场空。
今年有很多人在向我咨询转码的时候，都非常焦虑，最焦虑的一个问题就是到 35 岁是不是就意味着失业，是不是要跳槽其它行业，哪怕他们还只是在校的大学生，20 岁出头的样子，距离 35 岁还有十几年，便开始未雨绸缪的想着那个时间点的规划。
确实，35 岁，对于许多人来说，似乎是一个职业生涯的分水岭。
传统观念中，35 岁意味着稳定，意味着要有一定的职业成就，似乎一切都已经尘埃落定。
但对一些人来说，这也可能是一个重新出发的节点，或许是生活所迫，或许是兴趣爱好，还是有一些人选择在临近 35 岁的时候做一次跳槽转型，有不少学员就是典型的例子。
A 学员开始转码的时候，已经快 35 岁了，一开始学的过程非常吃力，经常感觉脑细胞不够用了。
A 并不是技术出身，转型对他来说，最开始是一次巨大的挑战。每当遇到代码中那些复杂的逻辑和抽象的概念时，A 总感觉自己脑子转不过来。
数据结构的链表、树、图，这些对初学者来说本就艰深的概念，曾一度让他怀疑自己的选择。
尽管过程艰辛，三个月后，他成功收到了 offer 。
或许，对于他来说，35 岁是他的最后一次跳槽，跳槽到互联网行业，未来都在互联网行业耕耘。
...
回归我们公众号的主题。
继续来一道和「大厂秋招」相关的算法原题。
题目描述
平台：LeetCode
题号：931
题目描述：下降路径最小和
给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
示例 1：
输入：matrix = [[2,1,3],[6,5,4],[7,8,9]] 输出：13 解释：如图所示，为和最小的两条下降路径
示例 2：
输入：matrix = [[-19,57],[-40,-5]] 输出：-59 解释：如图所示，为和最小的下降路径
提示：
n == matrix.length == matrix[i].length-100 <= matrix[i][j] <= 100
解题思路
本题是典型的动态规划问题，使用动态规划的方式来逐层计算最小路径和。
- 使用一个二维数组
dp[i][j] 表示从第一行到达第 i 行第 j 列的最小路径和。
- 当前状态
dp[i][j] 可以由上一行的三个位置到达，即dp[i-1][j]（正上方）、dp[i-1][j-1]（左上方）、dp[i-1][j+1]（右上方）中的最小值加上当前位置的值： dp[i][j] = matrix[i - 1][j - 1] + min(dp[i - 1][j], dp[i - 1][j - 1], dp[i - 1][j + 1])
- 第1行的最小路径和就是第1行本身的元素值，因此初始化
dp[0][j] = matrix[0][j]。
- 当列在边界时，需要特别处理。比如，如果是第一列，那么左上角
dp[i-1][j-1]就不存在，因此可以设置为一个很大的值；同理，对于最右列，右上角dp[i-1][j+1]也需要特殊处理。
- 结果是最后一行的所有
dp[n-1][j]中的最小值，因为下降路径可以从最后一行的任意位置结束。
参考代码
class Solution:
def minFallingPathSum(self, matrix: List[List[int]]) -> int:
# 矩阵大小
n = len(matrix)
# 创建 dp 数组来存储每个位置的最小路径和
dp = [[0] * (n + 2) for _ in range(n + 1)]
# 初始化边界的值为无穷大，防止越界
for i in range(1, n + 1):
dp[i][0] = float('inf')
dp[i][n + 1] = float('inf')
# 动态规划计算 dp 数组
for i in range(1, n + 1):
for j in range(1, n + 1):
# 计算当前元素的最小下降路径和
dp[i][j] = matrix[i - 1][j - 1] + min(dp[i - 1][j], dp[i - 1][j - 1], dp[i - 1][j + 1])
# 从最后一行找到最小的路径和
return min(dp[n][1:n+1])
最后，为了帮助近期求职的朋友们，小灰制作了一份数据结构与算法的学习导图，欢迎扫码添加小灰的个人微信，备注“算法”。
2024年，还剩下最后三个多月，让我们一起共勉 💪。
