Rod Cutting [DP]
Dreagon
9161
Dynamic Programming

One of the famous DP question. This question also test the pure basic of dynamic programming.

Lets understand with an example:

length   | 1   2   3   4   5   6   7   8  
--------------------------------------------
price    | 1   5   8   9  10  17  17  20

Given a rod of length of n (here n=8) and its prices if it is sold in that many piece.
That is:

 If we sell 1 piece its price will be 1
 if we sell 2 piece its price will be 5
 Similarly:
	
	Pieces       Cost
	---------------------
	 3 piece =    8 
	 4 piece =    9
	 5 piece =   10
	 6 piece =   17
	 7 piece =   17
	 8 piece =   20

Now we have to find the way to cut the rod in pieces such that the profit obtained when sold becomes maximum.

Approach:
Now in the above example :
8 pieces = n
and its cost is 20. That is if the whole rod is sold without any cuts profit will be 20.

But is it the maximum profit , lets check:

Now :
Let's sell the rod in

pieces    cost
----------------
6 pieces = 17
2 pieces = 5
Total Profit  : 17+5 = 22

Code:

C++

Top-Down DP:

int rod(vector<int> prices,int n,int dp[]){  //  prices array , n =  length of the prices

    // base case
    if(n<=0)
        return 0;

    // lookup case
    if(dp[n]!=0)
        return dp[n];

    // recursive case
    int ans = INT_MIN;
    for (int i = 0; i < n;i++){
        int cut = i + 1; // done as the index is 0 based 
        int current_ans =  prices[i]+rod(prices,n-cut,dp);

        ans = max(ans, current_ans); 
    }

    return dp[n]=ans;
}

Bottom-Up DP:

int rod_cutting_bottom_up(vector<int> prices,int n){
    int dp[n+1];

    dp[0] = 0;
    
    for (int i = 1; i <= n;i++){
        int ans = INT_MIN;
        for (int j = 0; j < i;j++){
            int cut = j + 1;
            int current_ans = prices[j] + dp[i - cut];
            ans = max(ans, current_ans);
        }
        dp[i] = ans;
    }
    return dp[n];
}

Hope this helps.

Comments (3)