动态规划—最小距离路径—何时使用返回整数.MAX_VALUE并返回0

Question

我正在练习一个程序，求一个3x3矩阵到最后一个元素(2,2)的最小距离。

static int minCost(int cost[][], int m,int n)
{
if (n < 0 || m < 0)
return Integer.MAX_VALUE;
else if (m == 0 && n == 0)
return cost[m][n];
else
return cost[m][n] +
min( minCost(cost, m-1, n-1),
minCost(cost, m-1, n),
minCost(cost, m, n-1) );
}

给出了正确的答案8，但是，如果我使用return 0;而不是return Integer.MAX_VALUE;，我得到的结果是7。(return 0; \gives answer as 7return 1;//returning >0 values gives correct answer and <0(like -1-->gives 6,-2 -->gives 5 etc )我的驱动代码是

public static void main(String args[])
{

int cost[][] = { {1, 2, 3},
{4, 8, 2},
{1, 5, 3} };

System.out.print(minCost(cost, 2, 2));
}

我找不到问题。这是因为静态方法吗?请帮助。我正在使用在线java编译器从教程点。

Answer 1

在递归中，对于这部分代码:

return cost[m][n] + 
min(minCost(cost, m-1, n-1),
minCost(cost, m-1, n),
minCost(cost, m, n-1) );

当你执行return 0;时，对于第一个minCost递归调用，返回的值是0。由于您正在检查最小值，因此与其他minCost递归调用相比，0总是最小的，即使它们返回1。因此，为了让min函数确定三个minCost调用的正确最小值，您需要为退出策略返回Integer.MAX_VALUE。同样，如果你返回负(-1/-2等)，这将成为你的min函数的最小值。

希望这能解释清楚!