动态规划最小路径和问题：边界返回Integer.MAX_VALUE与0的区别

问题解答 #

首先明确结论 #

该问题和static修饰的方法完全无关，错误是由越界条件的返回值逻辑不符合最小路径求解规则导致的。

原因分析 #

你实现的递归逻辑是倒推计算从矩阵左上角(0,0)到目标坐标(m,n)的最小路径和，允许每次从左上、正上、正左三个方向转移到当前坐标。

• 当递归传入的m或n小于0时，代表当前路径已经走出了矩阵边界，属于无效路径，不能参与最小路径的选择。
• 初始代码返回Integer.MAX_VALUE的作用是：给无效路径设置一个极大的代价，这样调用min函数取最小值时，会自动排除这些无效路径，只在合法路径中选最小代价。

修改返回值后的错误逻辑 #

如果把越界返回值改成0或者负数：

• 无效路径的代价比多数合法路径的代价更小，min函数会错误地选择这些越界的无效路径参与计算，最终得到的总路径和自然会偏小，和你观察到的现象完全吻合：
  • 返回0时结果为7，是因为计算过程中多次选择了越界返回的0替代了原本更高的合法节点代价
  • 返回负数时代价比0更低，最终结果会进一步减小

修复方案 #

保留越界条件返回Integer.MAX_VALUE的逻辑即可，不需要修改方法的static修饰符。

内容的提问来源于stack exchange，提问作者eef cemp