text: Treasure and Cities | A memoization based program to find maximum treasure that can be collected . ; k is current index and col is previous color . ; if ( k == n ) base case ; if ( col == color [ k ] ) check if color of this city is equal to prev visited city ; return max of both options ; Driver code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 1001 ; int dp [ MAX ] [ MAX ] ; int MaxProfit ( int treasure [ ] , int color [ ] , int n , int k , int col , int A , int B ) { return dp [ k ] [ col ] = 0 ; if ( dp [ k ] [ col ] != -1 ) return dp [ k ] [ col ] ; int sum = 0 ; sum += max ( A * treasure [ k ] + MaxProfit ( treasure , color , n , k + 1 , color [ k ] , A , B ) , MaxProfit ( treasure , color , n , k + 1 , col , A , B ) ) ; else sum += max ( B * treasure [ k ] + MaxProfit ( treasure , color , n , k + 1 , color [ k ] , A , B ) , MaxProfit ( treasure , color , n , k + 1 , col , A , B ) ) ; return dp [ k ] [ col ] = sum ; } int main ( ) { int A = -5 , B = 7 ; int treasure [ ] = { 4 , 8 , 2 , 9 } ; int color [ ] = { 2 , 2 , 6 , 2 } ; int n = sizeof ( color ) / sizeof ( color [ 0 ] ) ; memset ( dp , -1 , sizeof ( dp ) ) ; cout << MaxProfit ( treasure , color , n , 0 , 0 , A , B ) ; return 0 ; }