Question -
Given a m x n matrix filled with non-negative numbers, find a path from top left to bottom right which minimises the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
#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;
}
Output
Min cost is -2147483647
Expected output
Min cost is 3
If I use below code instead of Line 1, 2 and 3 from the main program then answer is correct.
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));
Why this is happening ? Are not both codes same ? Any help will be appreciated.
arr[start_x][start_y] +off the computation of bothbottomandright, and add it to thereturncalculation, then they're equivalent. You're experiencing signed integer overflow with your first code, which invokes UB. In at least one case your first code triggers anINT_MAXreturn, which is then added toarr[start_x][start_y]and stored inbottom(orright). That addition is what is triggering the overflow, since anintcan't be bigger thanINT_MAX. - WhozCraig