本文详解递归求解二维迷宫从左上角到右下角的最小通行成本时的典型错误：未正确处理越界情形导致结果失真，并给出修复方案、完整可运行代码及记忆化优化指引。
本文详解递归求解二维迷宫从左上角到右下角的最小通行成本时的典型错误：未正确处理越界情形导致结果失真，并给出修复方案、完整可运行代码及记忆化优化指引。
在使用递归解决“迷宫最小成本路径”问题时，一个看似简洁的实现往往隐藏着关键逻辑漏洞。题设要求：从 (0, 0) 出发，仅允许向右（列+1）或向下（行+1）移动，每进入一格需支付对应单元格值作为成本，目标是抵达 (n−1, m−1) 时总成本最小。
原代码的核心缺陷在于越界处理缺失：
public static int findMinCost(int[][] maze, int row, int col) {
if(row == 0 && col == 0) {
return maze[row][col];
}
int cost = 0;
if(row >= 0 && col >= 0) { // ❌ 仅检查非负，未覆盖 row<p>问题本质：当 row 或 col 变为 -1（例如从 (0,1) 向左走、或从 (1,0) 向上走），递归调用进入非法坐标。此时 if(row >= 0 && col >= 0) 不成立，函数直接返回初始化的 cost = 0。这等价于“允许免费穿越边界”，导致算法误将无效路径纳入比较，从而得出偏小的错误结果。</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/ai/1131" title="HitPaw"><img
src="https://img.php.cn/upload/ai_manual/000/000/000/175680063848936.png" alt="HitPaw" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/ai/1131" title="HitPaw" class="overflowclass">HitPaw</a>
<p class="overflowclass">一款AI驱动的视频、图片编辑器</p>
</div>
<a rel="nofollow" href="/ai/1131" title="HitPaw" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div><p>✅ 正确做法：对所有越界情况（row 不可接受的极大值，确保其在 Math.min() 中被自然淘汰：</p><pre class="brush:php;toolbar:false;">public static int findMinCost(int[][] maze, int row, int col) {
// 基础情况：到达起点
if (row == 0 && col == 0) {
return maze[0][0];
}
// 关键修复：越界返回无穷大（不可选路径）
if (row <p>? <strong>注意事项</strong>：</p>
- 调用入口必须传入终点坐标：findMinCost(maze, n-1, m-1)；
- Integer.MAX_VALUE 是安全选择，但需注意后续加法可能溢出（本题成本为非负整数，且路径长度有限，通常无风险；若需更稳健，可用 Long.MAX_VALUE 并改用 long 返回类型）；
- 时间复杂度陷阱：朴素递归存在大量重复子问题（如 (i,j) 被多次计算），时间复杂度达 O(2^(n+m))，对稍大矩阵（如 20×20）即超时。
? 进阶优化：添加记忆化（Memoization）
引入二维 dp 数组缓存已计算结果，将时间复杂度降至 O(n×m)：
public static int findMinCostMemo(int[][] maze, int row, int col, int[][] memo) {
if (row == 0 && col == 0) return maze[0][0];
if (row <p>总结：递归解迷宫最小成本，<strong>边界守卫是前提，记忆化是标配</strong>。先确保逻辑正确性（用 Integer.MAX_VALUE 拒绝非法路径），再通过缓存提升效率，二者缺一不可。</p>
