使用递归在矩阵中寻找最小成本路径

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));      

为什么会出现这种情况？这两个代码不是一样的吗？任何帮助都将不胜感激。

- tush

---

它们不是等价的。如果你将 arr[start_x][start_y] + off 移动到 bottom 和 right 的计算之外，并将其添加到 return 计算中，那么它们就是等价的。你的第一个代码会导致有符号整数溢出，从而引发 UB。在至少一种情况下，你的第一个代码会触发 INT_MAX 返回，然后将其添加到 arr[start_x][start_y] 中并存储在 bottom（或 right）中。这个加法触发了溢出，因为 int 不能比 INT_MAX 更大。 - WhozCraig

Answer 1

如果你记录下第一种解法执行的递归调用，你会发现无效答案(-2147483647)是由于将矩阵的最后一个元素(1)加到INT_MAX上所导致的，而INT_MAX是第一次递归退出时返回的值。

下面，min_cost(x, y)[z]表示使用start_x=x、start_y=y调用min_cost，并且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将返回较小的值，仅在此之后将其添加到当前矩阵单元格中的值中（而不是首先将其与当前单元格中的值相加，从而产生溢出并传递错误结果）。

- Polb