CODEWITHSUNDEEP
c++algorithmdynamic-programming
tush
tush

Reputation: 59

Minimum cost path in matrix using recursion

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.

Upvotes: 3

Views: 852

Answers (1)

Polb
Polb

Reputation: 700

If you write down the recursive calls that are executed during your first solution, you will see that the invalid answer (-2147483647) emerges from adding the last element of the matrix (1) to INT_MAX, which is the value returned by your first recursion exit case.

Below, min_cost(x, y)[z] denotes the call of min_cost with start_x=x, start_y=y, z being the index of this recursive call (first call, second call etc.)

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

The last two calls will make call indexed [1] to return min(1+INT_MAX, 1+1), which will be 1+INT_MAX, which is actually INT_MIN, because of integer overflow.

At this point, the first recursive branch of the call indexed [0] is computed, so min_cost(0, 0)[0] will have to choose between 1+INT_MIN and the second branch result (which we did not unroll here). 1+INT_MIN will be at least as small as the result of the second branch, so this is what your first algorithm returns - 1+INT_MIN.

Your second version of the algorithm produces the correct result, since the result of the recursive call that previously returned INT_MAX will now get compared against the second result, in this line: min(min_cost(...), min_cost(...)). If it is first compared against a value smaller than it, then min will return the smaller value and only after that add it to the value in the current matrix cell (instead of first adding it with the value in the current cell, producing an overflow an passing over the wrong result).

Upvotes: 2

Related Questions