昨天看到一个网友的吐槽，真是让我忍不住笑出声——“一觉醒来，美团的offer作废了。”
网友表示前天HR催着交两方，他想着反正也没急着确认，想着再等等，毕竟手里的其他几个大厂offer还没开奖。结果一觉醒来，邮件通知——offer超时作废，瞬间从喜提大厂到全盘皆输，感觉心态都崩了。
算法题：矩阵中的最长递增路径
深度优先搜索 + 记忆化搜索
算法步骤
我们会定义一个二维的 dp数组，用来存储从每个位置出发的最长递增路径。对每个位置 (i, j)，我们尝试从四个方向（上、下、左、右）出发，递归地查找递增路径。如果已经计算过该位置，直接返回结果。最后，遍历整个矩阵，求得最长路径。
def longestIncreasingPath(matrix):
if not matrix:
return 0
rows, cols = len(matrix), len(matrix[0])
# dp数组存储从某个位置出发的最长递增路径
dp = [[-1] * cols for _ in range(rows)]
# 定义四个方向的移动
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# 辅助函数，利用DFS和记忆化搜索
def dfs(x, y):
# 如果已经计算过，直接返回
if dp[x][y] != -1:
return dp[x][y]
max_length = 1 # 每个位置至少有一个长度为1的路径
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < rows and 0 <= ny < cols and matrix[nx][ny] > matrix[x][y]:
max_length = max(max_length, 1 + dfs(nx, ny))
dp[x][y] = max_length
return dp[x][y]
# 遍历整个矩阵，计算最长路径
longest_path = 0
for i in range(rows):
for j in range(cols):
longest_path = max(longest_path, dfs(i, j))
return longest_path
代码解析
dp数组：用来记忆化搜索，避免重复计算。如果dp[i][j] != -1，表示从(i, j)出发的最长递增路径已经计算过了。dfs(x, y)：深度优先搜索，递归计算从(x, y)位置出发的最长递增路径。如果某个位置已经计算过，我们直接返回之前存储的结果；否则，我们探索四个方向，计算每个方向的最长路径。longest_path：我们遍历整个矩阵的每个位置，计算每个位置出发的最长路径，并更新最终的最长路径。
时间复杂度分析
O(m * n)，其中 m 是矩阵的行数，n 是矩阵的列数。每个位置最多计算一次，而且我们通过记忆化搜索避免了重复计算，效率还是蛮高的。代码优化和改进
对编程、职场感兴趣的同学，大家可以联系我微信：golang404，拉你进入“程序员交流群”。
虎哥作为一名老码农，整理了全网最全《python高级架构师资料合集》。
