深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。它从一个顶点开始，尽可能深地搜索树的分支。深度优先搜索沿着一条路径深入，直到无法继续为止，然后回溯并尝试其他路径。这种搜索策略可以系统地探索一个图的所有顶点和边。
深度优先搜索的主要特点包括：
-
递归实现：深度优先搜索通常使用递归实现，其中每个节点会递归地访问其所有未访问过的邻居节点。
-
栈的使用：在非递归实现中，可以使用栈（后进先出的数据结构）来模拟递归过程。
-
路径探索：深度优先搜索会沿着一条路径深入探索，直到到达一个没有未访问邻居的节点，然后回溯。
-
回溯：当搜索到达一个死胡同（即没有更多的节点可以访问）时，算法会回溯到上一个节点，并尝试另一条路径。
-
图的遍历：在图的遍历中，深度优先搜索可以用来检测环，或者确定图是否是连通的。
-
时间复杂度：对于有V个顶点和E条边的图，深度优先搜索的时间复杂度通常是O(V+E)。
-
应用场景：深度优先搜索常用于解决迷宫问题、路径寻找、拓扑排序、检测图中的环等问题。
深度优先搜索的伪代码如下：
DFS(graph, vertex, visited):visited[vertex] = truefor each neighbor of vertex:if visited[neighbor] == false:DFS(graph, neighbor, visited)在实际应用中，深度优先搜索可以用于各种图和树结构的问题，是计算机科学中一个非常重要的算法
滑雪场
题目描述
这是一道经典的二维矩阵搜索问题。题目描述了一个滑雪场景：
-
给定一个二维矩阵，每个位置表示滑雪场的海拔高度
-
滑雪者可以从任意位置开始滑雪
-
滑雪者只能从高处往低处滑
-
每次可以向上下左右四个方向滑动
-
要求找出最长的滑雪路径长度
示例说明
以代码中的测试用例为例：
test_heights = [[1, 2, 3, 4, 5],[16, 17, 18, 19, 6],[15, 24, 25, 20, 7],[14, 23, 22, 21, 8],[13, 12, 11, 10, 9]
]在这个例子中：
-
最长的滑雪路径长度是25
-
一条可能的最长路径是：25 → 24 → 23 → 22 → 21 → 20 → 19 → 18 → 17 → 16 → 15 → 14 → 13 → 12 → 11 → 10 → 9 → 8 → 7 → 6 → 5 → 4 → 3 → 2 → 1
问题特点
-
路径特性：
-
路径必须是严格下降的（每一步都必须比上一步的高度低）
-
路径长度包含起点和终点
-
搜索特性：
-
需要尝试从每个点出发
-
每个点都可能是最长路径的起点
-
具有重叠子问题的特点
-
解题难点：
-
如何避免重复计算
-
如何处理边界情况
-
如何高效地搜索所有可能的路径
解题思路
-
使用DFS：
-
采用深度优先搜索遍历所有可能的路径
-
从每个点开始尝试四个方向的滑行
-
记忆化优化：
-
使用memo数组记录已经计算过的结果
-
避免重复计算相同的子问题
-
边界处理：
-
检查数组边界
-
检查高度条件
-
处理无效输入
实现代码
def longestSkiPath(heights):if not heights or not heights[0]:return 0rows = len(heights)cols = len(heights[0])# 记忆化数组，memo[i][j] 表示从点(i,j)开始能滑行的最长路径长度memo = [[-1] * cols for _ in range(rows)]# 四个方向：上、下、左、右directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]def dfs(row, col):# 如果已经计算过，直接返回if memo[row][col] != -1:return memo[row][col]# 初始长度为1（当前点）max_length = 1# 尝试四个方向for dx, dy in directions:new_row, new_col = row + dx, col + dy# 检查新位置是否有效且高度更低if (0 <= new_row < rows and 0 <= new_col < cols and heights[new_row][new_col] < heights[row][col]):# 递归计算从新位置开始的最长路径current_length = 1 + dfs(new_row, new_col)max_length = max(max_length, current_length)# 记录结果memo[row][col] = max_lengthreturn max_length# 从每个点开始尝试，找到最长路径result = 0for i in range(rows):for j in range(cols):result = max(result, dfs(i, j))return result# 测试代码
if __name__ == "__main__":# 测试用例test_heights = [[1, 2, 3, 4, 5],[16, 17, 18, 19, 6],[15, 24, 25, 20, 7],[14, 23, 22, 21, 8],[13, 12, 11, 10, 9]]print(longestSkiPath(test_heights)) # 应该输出 25 从点(2,2)（值为25）开始的搜索过程：
-
检查四周：
-
上：18 < 25 ✓
-
下：22 < 25 ✓
-
左：24 < 25 ✓
-
右：20 < 25 ✓
-
递归搜索每个可行方向，并选择最长的路径：
-
从18继续搜索
-
从22继续搜索
-
从24继续搜索
-
从20继续搜索
-
使用记忆化数组（memo）避免重复计算：
-
当某个点被计算过后，其结果会被存储在memo中
-
下次遇到相同的点时直接返回存储的结果
5. 时间复杂度
-
没有记忆化：O(4^(mn))，因为每个点都可能往4个方向扩展
-
使用记忆化后：O(mn)，因为每个点最多被计算一次
6. 空间复杂度
-
O(mn)，主要是记忆化数组的空间
这个算法通过记忆化搜索有效地避免了重复计算，大大提高了效率。对于示例输入，最终会找到长度为25的最长路径。