Top-down DP求解01 Matrix问题遇挫，求原因与优化方案
问题背景
刚接触动态规划，正在做01 Matrix问题：
给定一个m×n的二进制矩阵mat，返回每个单元格到最近的0的距离，相邻单元格间的距离为1。
我尝试用带记忆化的DFS（Top-Down动态规划）求解，但部分测试用例无法通过。算法逻辑是：找到矩阵中的'1'后，向四个方向进行深度优先搜索，取四个方向结果的最小值加1，存入记忆化表ans[][]。
查了相关解法后发现几乎都是Bottom-Up实现，想请教：为什么四向取最小+记忆化无法得到最优解？我的解法存在哪些缺失？
以下是我的代码：
class Solution { public int[][] updateMatrix(int[][] mat) { int m = mat.length; int n = mat[0].length; int[][] ans = new int[m][n]; for(int i = 0; i <m; i++){ for(int j = 0; j <n; j++){ if(mat[i][j] == 0){ ans[i][j] = 0; } else{ ans[i][j] = -1; } } } for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(ans[i][j] == - 1){ boolean[][] visited = new boolean[m][n]; ans[i][j] = dfs(i, j, m, n, mat, ans, visited); } } } for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ boolean[][] visited = new boolean[m][n]; ans[i][j] = Math.min(ans[i][j], dfs(i, j, m, n, mat, ans, visited)); } } return ans; } public int dfs(int i, int j, int m, int n, int[][]mat, int[][] ans, boolean[][] visited){ if(i >= m || i < 0 || j >=n || j < 0|| visited[i][j]){ return Integer.MAX_VALUE; } if(mat[i][j] == 0){ return 0; } if(ans[i][j] != -1){ return ans[i][j]; } visited[i][j] = true; int up = dfs(i - 1, j, m, n, mat, ans, visited); int down = dfs(i + 1, j, m, n, mat, ans, visited); int left = dfs( i, j - 1, m, n, mat, ans, visited); int right = dfs(i, j + 1, m, n, mat, ans,visited); visited[i][j] = false; ans[i][j] = Math.min (up, Math.min(down, Math.min(left, right))) + 1; return ans[i][j]; } }
你的解法核心问题分析
1. 递归栈溢出风险
这是导致大测试用例失败的直接原因。对于规模较大的矩阵（比如1000×1000），DFS的递归深度可能超过Java虚拟机的默认栈容量（通常约1024），直接触发StackOverflowError，程序崩溃。
2. 冗余计算与无效逻辑
代码中的第二次循环完全没有意义：当第一次循环完成后，ans数组中所有单元格都已被赋值，此时调用dfs会直接返回ans[i][j]（因为ans[i][j] != -1），Math.min(ans[i][j], dfs(...))等价于原地赋值，浪费大量时间。
3. 内存开销过大
每次调用dfs都创建一个全新的m×n大小的visited数组，对于大矩阵来说，这会带来巨大的内存和时间开销，进一步降低运行效率。
4. 记忆化的潜在局限性（理论层面）
虽然你的逻辑在小矩阵中能得到正确结果，但Top-Down的记忆化方式依赖递归顺序：如果某个单元格的最优解依赖的邻居尚未被计算，DFS会递归到0再返回，理论上能得到正确值，但这种依赖关系的不确定性会导致递归深度不可控，还是会回到栈溢出的问题。
为什么Bottom-Up解法更适合？
这个问题的最优解（多源BFS、两次遍历DP）本质都是Bottom-Up思路，原因在于：
- 多源BFS：将所有0的位置加入队列，逐层向外扩散，每个单元格第一次被访问时就得到了到最近0的最短距离，天然避免递归，无栈溢出风险。
- 两次遍历DP：先从左上到右下，用
dp[i][j] = min(dp[i][j], min(dp[i-1][j], dp[i][j-1]) + 1)更新；再从右下到左上，用dp[i][j] = min(dp[i][j], min(dp[i+1][j], dp[i][j+1]) + 1)补全四个方向的最小值，全程迭代，效率极高。
若坚持用Top-Down的修正思路
如果一定要用DFS实现，可做以下优化（但仍无法解决大矩阵栈溢出问题）：
- 移除冗余的第二次循环；
- 用
ans数组本身标记未处理状态（比如初始设为Integer.MAX_VALUE），避免重复创建visited数组； - 先确保邻居的最优解已计算，再更新当前单元格值。
修正后的示例代码：
class Solution { private int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}}; public int[][] updateMatrix(int[][] mat) { int m = mat.length; int n = mat[0].length; int[][] ans = new int[m][n]; // 初始化为无穷大表示未处理 for(int i = 0; i < m; i++){ Arrays.fill(ans[i], Integer.MAX_VALUE); } // 先标记所有0的位置 for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(mat[i][j] == 0){ ans[i][j] = 0; } } } // 处理所有未标记的1 for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(ans[i][j] == Integer.MAX_VALUE){ dfs(i, j, m, n, mat, ans); } } } return ans; } public int dfs(int i, int j, int m, int n, int[][]mat, int[][] ans){ if(i < 0 || i >= m || j <0 || j >=n){ return Integer.MAX_VALUE; } // 已处理过直接返回 if(ans[i][j] != Integer.MAX_VALUE){ return ans[i][j]; } // 先递归处理四个方向，确保邻居的最优解已计算 int minDist = Integer.MAX_VALUE; for(int[] dir : dirs){ int ni = i + dir[0]; int nj = j + dir[1]; int dist = dfs(ni, nj, m, n, mat, ans); if(dist != Integer.MAX_VALUE){ minDist = Math.min(minDist, dist + 1); } } ans[i][j] = minDist; return minDist; } }
内容的提问来源于stack exchange，提问作者Spindoctor
