text: Cutting a Rod | DP | CPP program for above approach ; Global Array for the purpose of memoization . ; A recursive program , using , memoization , to implement the rod cutting problem ( Top - Down ) . ; The maximum price will be zero , when either the length of the rod is zero or price is zero . ; If the length of the rod is less than the maximum length , Max_lene will consider it . Now depending upon the profit , either Max_lene we will take it or discard it . ; If the length of the rod is greater than the permitted size , Max_len we will not consider it . ; Max_lene Max_lenill return the maximum value obtained , Max_lenhich is present at the nth roMax_len and Max_lenth column . ; Driver program to test above functions ; Function Call
code: #include <iostream> NEW_LINE using namespace std ; int t [ 9 ] [ 9 ] ; int un_kp ( int price [ ] , int length [ ] , int Max_len , int n ) { if ( n == 0 Max_len == 0 ) { return 0 ; } if ( length [ n - 1 ] <= Max_len ) { t [ n ] [ Max_len ] = max ( price [ n - 1 ] + un_kp ( price , length , Max_len - length [ n - 1 ] , n ) , un_kp ( price , length , Max_len , n - 1 ) ) ; } else { t [ n ] [ Max_len ] = un_kp ( price , length , Max_len , n - 1 ) ; } return t [ n ] [ Max_len ] ; } int main ( ) { int price [ ] = { 1 , 5 , 8 , 9 , 10 , 17 , 17 , 20 } ; int n = sizeof ( price ) / sizeof ( price [ 0 ] ) ; int length [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { length [ i ] = i + 1 ; } int Max_len = n ; cout << " Maximum ▁ obtained ▁ value ▁ is ▁ " << un_kp ( price , length , n , Max_len ) << endl ; }