Find the minimum difference path from ( 0 , 0 ) to ( N | C ++ implementation of the approach ; Function to return the minimum difference path from ( 0 , 0 ) to ( N - 1 , M - 1 ) ; Terminating case ; Base case ; If it is already visited ; Recursive calls ; Return the value ; Driver code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAXI  50 NEW_LINE int dp [ MAXI ] [ MAXI ] [ MAXI * MAXI ] ; int n , m ; int minDifference ( int x , int y , int k , vector < vector < int > > b , vector < vector < int > > c ) { if ( x >= n or y >= m ) return INT_MAX ; if ( x == n - 1 and y == m - 1 ) { int diff = b [ x ] [ y ] - c [ x ] [ y ] ; return min ( abs ( k - diff ) , abs ( k + diff ) ) ; } int & ans = dp [ x ] [ y ] [ k ] ; if ( ans != -1 ) return ans ; ans = INT_MAX ; int diff = b [ x ] [ y ] - c [ x ] [ y ] ; ans = min ( ans , minDifference ( x + 1 , y , abs ( k + diff ) , b , c ) ) ; ans = min ( ans , minDifference ( x , y + 1 , abs ( k + diff ) , b , c ) ) ; ans = min ( ans , minDifference ( x + 1 , y , abs ( k - diff ) , b , c ) ) ; ans = min ( ans , minDifference ( x , y + 1 , abs ( k - diff ) , b , c ) ) ; return ans ; } int main ( ) { n = 2 , m = 2 ; vector < vector < int > > b = { { 1 , 4 } , { 2 , 4 } } ; vector < vector < int > > c = { { 3 , 2 } , { 3 , 1 } } ; memset ( dp , -1 , sizeof ( dp ) ) ; cout << minDifference ( 0 , 0 , 0 , b , c ) ; return 0 ; }