递归------深度优先搜索

深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。它从一个顶点开始，尽可能深地搜索树的分支。深度优先搜索沿着一条路径深入，直到无法继续为止，然后回溯并尝试其他路径。这种搜索策略可以系统地探索一个图的所有顶点和边。

深度优先搜索的主要特点包括：

递归实现：深度优先搜索通常使用递归实现，其中每个节点会递归地访问其所有未访问过的邻居节点。
栈的使用：在非递归实现中，可以使用栈（后进先出的数据结构）来模拟递归过程。
路径探索：深度优先搜索会沿着一条路径深入探索，直到到达一个没有未访问邻居的节点，然后回溯。
回溯：当搜索到达一个死胡同（即没有更多的节点可以访问）时，算法会回溯到上一个节点，并尝试另一条路径。
图的遍历：在图的遍历中，深度优先搜索可以用来检测环，或者确定图是否是连通的。
时间复杂度：对于有V个顶点和E条边的图，深度优先搜索的时间复杂度通常是O(V+E)。
应用场景：深度优先搜索常用于解决迷宫问题、路径寻找、拓扑排序、检测图中的环等问题。

深度优先搜索的伪代码如下：

DFS(graph, vertex, visited):
    visited[vertex] = true
    for 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 0
    
    rows = 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_length
        return max_length
    
    # 从每个点开始尝试，找到最长路径
    result = 0
    for 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的最长路径。

秒客网