c++ - 使用递归的矩阵中的最小成本路径

Question

问题-

给定一个充满非负数的 m x n 矩阵，找到一条从左上角到右下角的路径，该路径最小化沿其路径的所有数字的总和。

注意:在任何时间点您只能向下或向右移动。

#include<iostream>
#include<climits>
using namespace std;

int min_cost(int arr[][2], int start_x, int start_y, int end_x, int end_y)
{
    if(start_x > end_x || start_y > end_y)
      return INT_MAX;

    if( start_x == end_x && start_y == end_y)
      return arr[end_x][end_y];

    int bottom = arr[start_x][start_y] + min_cost(arr, start_x + 1, start_y, end_x, end_y); // Line 1
    int right = arr[start_x][start_y] + min_cost( arr, start_x, start_y + 1, end_x, end_y);  // Line 2

    return min( bottom, right);   // Line 3 
}
int main()
{
    int arr[2][2] = { {1,2},
                      {1,1},
                    };
    cout <<"Min cost is " <<  min_cost(arr, 0, 0, 1, 1);
    return 0;
}

输出

 Min cost is -2147483647 

预期输出

Min cost is 3

如果我使用下面的代码而不是主程序中的第 1、2 和 3 行，那么答案是正确的。

return arr[start_x][start_y] + min( min_cost(arr, start_x + 1, start_y, end_x, end_y), 
                                    min_cost( arr, start_x, start_y + 1, end_x, end_y));      

为什么会发生这种情况？两个代码不一样吗？任何帮助将不胜感激。

Answer 1

如果您记下第一个解决方案期间执行的递归调用，您将看到将矩阵 (1) 的最后一个元素添加到 INT_MAX 中时会出现无效答案 (-2147483647)，这是由你的第一个递归退出案例。

下面，min_cost(x, y)[z]表示调用min_cost，其中start_x=x, start_y=y，z 是此递归调用的索引(第一次调用、第二次调用等)

min_cost(0, 0)[0] -> min(1 + min_cost(1, 0)[1], 1 + min_cost(0, 1)[2])

min_cost(1, 0)[1] -> min(1 + min_cost(2, 0)[3], 1 + min_cost(1, 1)[4])
min_cost(2, 0)[3] -> INT_MAX
min_cost(1, 1)[4] -> 1

最后两个调用将使索引为 [1] 的调用返回 min(1+INT_MAX, 1+1)，即 1+INT_MAX，即实际上INT_MIN，因为整数溢出。

此时，索引为 [0] 的调用的第一个递归分支已计算完毕，因此 min_cost(0, 0)[0] 必须在 1+INT_MIN< 之间进行选择 和第二个分支结果(我们没有在这里展开)。 1+INT_MIN 将至少与第二个分支的结果一样小，因此这就是您的第一个算法返回的结果 - 1+INT_MIN。

您的算法的第二个版本会产生正确的结果，因为之前返回 INT_MAX 的递归调用的结果现在将与第二个结果进行比较，在这一行中:min( min_cost(...), min_cost(...))。如果首先将其与小于它的值进行比较，则 min 将返回较小的值，并且仅在此之后将其添加到当前矩阵单元中的值(而不是首先将其与中的值相加)当前单元格，产生溢出并传递错误的结果)。