leetcode 最短路径
最新回答
青春期躁动症
2026-05-15 15:09:42
LeetCode上不同场景的最短路径问题需采用动态规划、BFS或Dijkstra算法等针对性方法解决，具体方案如下：
1. 三角形最小路径和（问题120）该问题要求从三角形顶部到底部的最小路径和，核心思路是通过动态规划自底向上计算。
- 动态规划状态定义：使用二维数组dp[i][j]表示从第i行第j列到底部的最小路径和。
- 状态转移方程：
每层最左节点（j=0）：dp[i][j] = dp[i+1][j] + triangle[i][j]；
每层最右节点（j=当前层最大索引）：dp[i][j] = dp[i+1][j-1] + triangle[i][j]；
其他节点：dp[i][j] = min(dp[i+1][j], dp[i+1][j-1]) + triangle[i][j]。
- 优化：空间复杂度可降至O(n)，仅需维护一维数组存储下一层结果。
- 示例：输入三角形[[2],[3,4],[6,5,7],[4,1,8,3]]，输出最小路径和为11（路径2→3→5→1）。
该问题要求在二进制矩阵中从起点到终点的最短路径，需满足路径所有单元格为0且八方向连通，广度优先搜索（BFS）是核心方法。
- 八方向BFS：从起点出发，每次向上下左右及对角线八个方向扩展，记录步数。
- 终止条件：首次到达终点时，当前步数即为最短路径长度。
- 示例：输入grid = [[0,0,0],[1,1,0],[1,1,0]]，输出4（路径：(0,0)→(0,1)→(0,2)→(1,2)→(2,2)）。
- 注意：若终点不可达，返回-1。
该问题允许消除最多k个障碍物，需结合BFS与状态记录。
- 状态设计：队列存储(x, y, remaining_k)，访问数组visited[x][y][k]记录到达(x,y)时剩余的消除次数。
- 关键条件：若相同位置被多次访问，优先保留剩余k更大的路径（或更小的步数）。
- 示例：在3x3网格中，起点(0,0)到终点(2,2)，k=1时，最短路径可能为6步（消除1个障碍物）。
该问题要求动态添加边并查询最短路径，需实现堆优化的Dijkstra算法。
- 核心数据结构：优先队列（最小堆）存储(current_cost, node)，距离数组dist[node]记录最小代价。
- 算法流程：
初始化所有节点距离为无穷大；
将起点加入堆，距离设为0；
每次从堆中取出代价最小的节点，更新其邻居的最小距离；
重复直到堆为空。
- 时间复杂度：O(mlogm)（m为边数），适用于稀疏图。
- 示例：添加边(1,2,5)和(1,3,10)后，查询1→3的最短路径为10（直接路径）或更小值（若存在中间节点）。
- 动态规划适用于结构化路径（如三角形）；
- BFS适用于无权图的最短路径；
- Dijkstra算法适用于带权图的最短路径；
- 状态扩展的BFS适用于含障碍消除的场景。根据问题特征选择合适方法，可高效解决LeetCode上的最短路径问题。
热门标签
