Rod cutting problem (DP-02)

You are given a rod of length N units along with an array that contains the prices of all pieces of size smaller than N (1 to N). You need to find out the maximum profit that can be obtained by cutting the rod into pieces and then selling it.

Sample Input: Prices – [ 1, 5, 8, 9, 10, 17, 17, 20 ], N = 8
Expected Output: 22
Explanation: The rod can be cut into two pieces of size 2 and 6 with total profit as 22.

Algorithm:

1. We will use dynamic programming to solve this problem. Create a DP array of size N+1 intialized to 0.
2. Iterate for all sizes starting from 1 to N.
3. For each size, consider all sizes less than or equal to the current size.
4. If we take size j ( j<=i, where i is the length of the rod ) and cut the rod into two pieces of size j and ( i – j ), the result will be maximum of DP[ i ] and ( prices[ j ] + DP[ i – j ] ). We do this for all j from 1 to i and for all i from 1 to N. We keep storing the result for each subproblem in the DP array and return the final result stored in DP[ N ].

#include <bits/stdc++.h>
using namespace std;

int helper(vector<int> prices, int n){
	vector<int> dp(n+1, 0);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=i; j++){
			dp[i] = max(dp[i], prices[j-1] + dp[i-j]);
		}
	}
	return dp[n];
}

int main(){
	vector<int> prices = {1, 5, 8, 9, 10, 17, 17, 20};
	int n=4;
	cout<<helper(prices, n);
	return 0;
}

Also take a look at another popular interview question Maximum Sum Subarray.