Home » Interview coding problems/challenges

# Rod Cutting

**Rod Cutting**: Here, we are going to learn how to maximize profit by cutting rod with dynamic programming?

Submitted by Radib Kar, on February 18, 2020

**Description:**

In this article we are going to see **how to maximize profit by cutting rod with dynamic programming?** This is a classic DP problem featured in many interview rounds of Amazon, Samsung etc.

**Problem statement:**

Given a rod of length **N** inches and an array of prices that contains prices for all pieces of size smaller than **n**. Determine the maximum value obtainable by cutting up the rod and selling the pieces.

Input: First input line consists of N, denoting the size of array. Second line of price of i^{th}length piece. Output: Print maximum price that can be obtained by selling the pieces.

**Example:**

Input: Length of rod: 8 Prices of pieces: 1 5 6 9 12 15 13 20 Output: maximum price that can be obtained: 20

**Explanation:**

Let us first understand the input format

Each element in the array represent price of length i where i is the index (considering 1-indexing).

So, for the above example:

Price of length 1: 1 (arr[0]) Price of length 2: 5 (arr[1]) Price of length 3: 6 (arr[2]) Price of length 4: 9 (arr[3]) Price of length 5: 12 (arr[4]) Price of length 6: 15 (arr[5]) Price of length 7: 13 (arr[6]) Price of length 8: 20 (arr[7])

Now, the thing is cutting the rod recursively. Like you have to option;

- Cut of i
^{th}length and recur for remaining - Else don't cut of that length.

The recursive function can be written as:

f(n) = maximum (f(i)+f(n-i)) where 1 ≤ i< n

In the above example, it's found that if we don't cut into pieces, if we sell the whole rod as 1 piece, then it would maximize profit to 20. All other options will lead to less amount of profit.

Also, if we make 4 pieces of length 2, would have same profit, 20.

**Solution Approach:**

Let's convert the above recursion in to dynamic programing.

The sub-problem can be to solve for rod of length **i** where * 1<=i<=n *and we need to store the results of this sub-problems in a array, namely DP

- Declare
**DP[n+1]** **DP[0]=0**as the result for rod length 0 is 0.- Now we need to calculate
**DP[i]**which would be results for rod length**i**(subproblems) -
As a base case, initialize
**DP[i]**with**arr[i-1]**which is the result if we don't cut into smaller pieces and sell the whole rod(piece of length i).for(int i=1;i<=n;i++) dp[i]=a[i-1];

The reason behind**dp[i]=arr[i-1]**not**arr[i]**because in DP array we are following 1-indexing( like for**n=1**it's**DP[1]**) and for arr we are following 0-indexing(for**n=1**,**arr[0]**) -
Now, calculate
**DP[i]**which will be maximum profit for sub problem with length**i**

Here we will use the recursive relation mentioned above

To calculate**DP[i]**,for**2≤i≤n**,

if**i**is 1 that follows base case,no more pieces to cut downfor j=1 to i-1 dp[i]=maximum(dp[j]+dp[i-j]) end for

**DP[n]**is the final result which is maximum profit for rod length**n**.

We could have calculated through the recursive function, but needless to say that the recursion tree would have overlapping sub-problem resulting to exponential time complexity. Hence, we converted the recursion into DP and solved.

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; int rodcutting(vector < int > a, int n) { int dp[n + 1]; dp[0] = 0; for (int i = 1; i <= n; i++) dp[i] = a[i - 1]; for (int i = 2; i <= n; i++) { for (int j = 1; j < i; j++) { if (dp[i] < dp[j] + dp[i - j]) dp[i] = dp[j] + dp[i - j]; } } return dp[n]; } int main() { int n, item; cout << "Enter rod length:\n"; scanf("%d", & n); cout << "Enter prices for the pieces of ith length:\n"; vector < int > a; for (int j = 0; j < n; j++) { scanf("%d", & item); a.push_back(item); } cout << "Maximum profit can be earned is: " << rodcutting(a, n) << endl; return 0; }

**Output**

RUN 1: Enter rod length: 8 Enter prices for the pieces of ith length: 1 5 6 9 12 15 13 20 Maximum profit can be earned is: 20 RUN 2: Enter rod length: 7 Enter prices for the pieces of ith length: 4 5 6 3 21 15 13 Maximum profit can be earned is: 29

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions