{"id":3616,"date":"2023-07-24T19:36:09","date_gmt":"2023-07-24T14:06:09","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3616"},"modified":"2023-07-24T19:43:05","modified_gmt":"2023-07-24T14:13:05","slug":"rod-cutting-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/rod-cutting-problem\/","title":{"rendered":"Rod Cutting Problem"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#sample-test-cases\">Sample Test Cases<\/a><\/li><li><a href=\"#naive-approach\">Naive Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#memoization-based-approach\">Memoization Based Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#iterative-dynamic-programming-approach\">Iterative Dynamic Programming Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#practice-problem\">Practice Problem:<\/a><\/li><li><a href=\"#faqs\">FAQs<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-what-is-the-time-complexity-per-state-transition-of-the-dynamic-programming-approach\">Q.1: What is the time complexity per state transition of the Dynamic Programming approach?<\/a><\/li><li><a href=\"#q2-how-to-identify-that-a-problem-can-be-solved-by-dynamic-programming\">Q.2: How to identify that a problem can be solved by Dynamic Programming?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a rod of length <strong>n <\/strong>\u00a0and array <strong>prices <\/strong>of length n denoting the cost of pieces of the rod of length 1 to n, find the maximum amount that can be made if the rod is cut up optimally.<\/p>\n\n\n\n<h2 id=\"sample-test-cases\">Sample Test Cases<\/h2>\n\n\n\n<p>Input 1:<\/p>\n\n\n\n<p>n = 8, prices[] = [1, 3, 4, 5, 7, 9, 10, 11]\n\n\n\n<p>Output 1:<\/p>\n\n\n\n<p>12<\/p>\n\n\n\n<p>Explanation 1:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"327\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Cutting the rod\"  class=\"wp-image-3658 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Cutting-the-rod-1024x327.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Cutting-the-rod-1024x327.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Cutting-the-rod-300x96.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Cutting-the-rod-768x246.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Cutting-the-rod-380x122.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Cutting-the-rod-550x176.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Cutting-the-rod-800x256.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Cutting-the-rod-1160x371.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Cutting-the-rod.png 1354w\" ><\/figure>\n\n\n\n<p>Cutting the rod into 2 rods of length 2 and 6 gives us a cost of 3 + 9&nbsp; = 12, which is optimal.<\/p>\n\n\n\n<p>Input 2:<\/p>\n\n\n\n<p>n = 4, prices[] = [1, 1, 1, 6]\n\n\n\n<p>Output 2:<\/p>\n\n\n\n<p>6<\/p>\n\n\n\n<p>Explanation 2:<\/p>\n\n\n\n<p>It can be seen that performing no cuts and taking the entire rod as a whole can lead to the optimal answer of 6.<\/p>\n\n\n\n<h2 id=\"naive-approach\">Naive Approach<\/h2>\n\n\n\n<p>We can solve this problem naively with a recursive backtracking-based solution. By generating all possible configurations of different pieces and finding the maximum among them, we can get our optimal solution.<\/p>\n\n\n\n<p><strong>Code \/ Implementation:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-2\">C++ Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int maximumProfit(vector &lt; int > &amp; prices, int n) {\n  if (n == 0) {\n    return 0;\n  }\n  int maxProfit = INT_MIN;\n  for (int i = 1; i &lt;= n; i++) {\n    maxProfit = max(maxProfit, prices[i - 1] + maximumProfit(prices, n - i));\n  }\n  return maxProfit;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-2\">Java Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> public static int maximumProfit(int[] prices, int n) {\n   if (n == 0) {\n     return 0;\n   }\n   int maxProfit = Integer.MIN_VALUE;\n   for (int i = 1; i &lt;= n; i++) {\n     maxProfit = Math.max(maxProfit, prices[i - 1] + maximumProfit(prices, n - i));\n   }\n   return maxProfit;\n }<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-2\">Python Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def maximumProfit(prices, n):\n    if n == 0:\n        return n\n    maxProfit = -999999\n    for i in range(1, n + 1):\n        maxProfit = max(maxProfit, prices[i - 1] + maximumProfit(prices, n - i))\n    return maxProfit<\/pre>\n\n\n\n<p><strong>Complexity Analysis<\/strong>:<\/p>\n\n\n\n<ul><li>Time Complexity: Exponential<\/li><li>Space Complexity: O(1) if recursion stack space is not considered<\/li><\/ul>\n\n\n\n<h2 id=\"memoization-based-approach\">Memoization Based Approach<\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"1016\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"recursion tree\"  class=\"wp-image-3660 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/recursion-tree-1024x1016.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/recursion-tree-1024x1016.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/recursion-tree-300x298.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/recursion-tree-150x150.png 150w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/recursion-tree-768x762.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/recursion-tree-80x80.png 80w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/recursion-tree-110x110.png 110w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/recursion-tree-380x377.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/recursion-tree-550x546.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/recursion-tree-800x794.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/recursion-tree-1160x1151.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/recursion-tree.png 1354w\" ><\/figure>\n\n\n\n<p>Considering the above recursion tree for n = 4, we can observe that there are multiple values, for which the function is being called again and again. Rather than using these redundant function calls, we can calculate the value of the function call once, and memoize it to use for future operations. Just by memoizing the results using an <strong>array<\/strong> or a <strong>hashmap<\/strong>, we can reduce the time complexity of the program from exponential to polynomial time complexity.<\/p>\n\n\n\n<p>Now to memoize the function calls, into some relevant data structure, we need to find out our <strong>DP states<\/strong>. Here, we find from the above diagram that the overlapping subproblem depends only on the length of the current piece of the rod (<strong>n<\/strong>). So, our DP state will be the optimal cost which can be obtained if the length of the rod is <strong>n<\/strong>. This leads us to a <strong>1D DP<\/strong> solution, which has,<\/p>\n\n\n\n<ul><li><strong>O(n)<\/strong> states<\/li><li><strong>O(n)<\/strong> time per transition&nbsp;&nbsp;<\/li><\/ul>\n\n\n\n<p><strong>Implementation:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-3\">C++ Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int maximumProfit(vector &lt; int > &amp; prices, int n, vector &lt; int > &amp; dp) {\n  if (n == 0) {\n    return 0;\n  }\n  if (dp[n] != -1) {\n    return dp[n];\n  }\n  int maxProfit = INT_MIN;\n  for (int i = 1; i &lt;= n; i++) {\n    maxProfit = max(maxProfit, prices[i - 1] + maximumProfit(prices, n - i, dp));\n  }\n  return dp[n] = maxProfit;\n}\nint getMaxProfit(vector &lt; int > &amp; a, int n) {\n  vector &lt; int > dp(n + 1, -1);\n  return maximumProfit(a, n, dp);\n}<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-3\">Java Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static int maximumProfit(int[] prices, int n, int[] dp) {\n  if (n == 0) {\n    return 0;\n  }\n  if (dp[n] != -1) {\n    return dp[n];\n  }\n  int maxProfit = Integer.MIN_VALUE;\n  for (int i = 1; i &lt;= n; i++) {\n    maxProfit = Math.max(maxProfit, prices[i - 1] + maximumProfit(prices, n - i, dp));\n  }\n  return dp[n] = maxProfit;\n}\npublic static int getMaxProfit(int[] a, int n) {\n  int[] dp = new int[n + 1];\n  for (int i = 0; i &lt;= n; i++) {\n    dp[i] = -1;\n  }\n  return maximumProfit(a, n, dp);\n}<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-3\">Python Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def maximumProfit(prices, n, dp):\n    if n == 0:\n        return n\n    if dp[n] != -1:\n        return dp[n]\n    maxProfit = -999999\n    for i in range(1, n + 1):\n        maxProfit = max(maxProfit, prices[i - 1] + maximumProfit(prices, n - i, dp))\n    dp[n] = maxProfit\n    return dp[n]\n\n\ndef getMaxProfit(prices, n):\n    dp = [-1] * (n + 1)\n    return maximumProfit(prices, n, dp)<\/pre>\n\n\n\n<p><strong>Complexity Analysis:<\/strong><\/p>\n\n\n\n<ul><li>Time Complexity: O(n<sup>2<\/sup>)<\/li><li>Space Complexity: O(n)<\/li><\/ul>\n\n\n\n<h2 id=\"iterative-dynamic-programming-approach\">Iterative Dynamic Programming Approach<\/h2>\n\n\n\n<p>Similar to the memoization approach, we can also solve this problem using tabulation-based Dynamic Programming. In any dynamic programming problem, there are 2 things that are to be considered,<\/p>\n\n\n\n<ul><li>States: <strong>DP[i]<\/strong> = Best possible price for a rod of length i.<\/li><li>Transitions: <strong>DP[i]<\/strong> = max(<strong>prices[j]<\/strong> + <strong>DP[i &#8211; j &#8211; 1]<\/strong>) overall values of j from <strong>[0, i &#8211; 1]<\/strong><\/li><\/ul>\n\n\n\n<p>Using the above states and transitions, we can tabulate the optimal answer for all possible lengths of the rod, and finally, our required result will be stored in DP[n].<\/p>\n\n\n\n<p><strong>Implementation:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int maximumProfit(vector &lt; int > &amp; prices, int n) {\n  vector &lt; int > dp(n + 1, 0);\n  if (n &lt;= 0) {\n    return 0;\n  }\n  int maxVal = INT_MIN;\n  for (int i = 1; i &lt;= n; i++) {\n    for (int j = 0; j &lt; i; j++) {\n      maxVal = max(maxVal, prices[j] + dp[i - j - 1]);\n    }\n    dp[i] = maxVal;\n  }\n  return dp[n];\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static int maximumProfit(int[] prices, int n) {\n  int[] dp = new int[n + 1];\n  if (n &lt;= 0) {\n    return 0;\n  }\n  int maxVal = Integer.MIN_VALUE;\n  for (int i = 1; i &lt;= n; i++) {\n    for (int j = 0; j &lt; i; j++) {\n      maxVal = Math.max(maxVal, prices[j] + dp[i - j - 1]);\n    }\n    dp[i] = maxVal;\n  }\n  return dp[n];\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def maximumProfit(prices, n):\n    dp = [0] * (n + 1)\n    if n &lt;= 0:\n        return 0\n    maxVal = -999999\n    for i in range(1, n + 1):\n        for j in range(i):\n            maxVal = max(maxVal, prices[j] + dp[i - j - 1])\n        dp[i] = maxVal\n    return dp[n]<\/pre>\n\n\n\n<p><strong>Complexity Analysis:<\/strong><\/p>\n\n\n\n<ul><li>Time Complexity: O(n<sup>2<\/sup>)<\/li><li>Space Complexity: O(n)<\/li><\/ul>\n\n\n\n<h2 id=\"practice-problem\">Practice Problem:<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/old\/problems\/rod-cutting\/\" target=\"_blank\">Rod Cutting<\/a><\/li><\/ul>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<h3 id=\"q1-what-is-the-time-complexity-per-state-transition-of-the-dynamic-programming-approach\"><span id=\"q-1-what-is-the-time-complexity-per-state-transition-of-the-dynamic-programming-approach\">Q.1: What is the time complexity per state transition of the Dynamic Programming approach?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>The time complexity is O(n) per transition.<\/p>\n\n\n\n<h3 id=\"q2-how-to-identify-that-a-problem-can-be-solved-by-dynamic-programming\"><span id=\"q-2-how-to-identify-that-a-problem-can-be-solved-by-dynamic-programming\">Q.2: How to identify that a problem can be solved by Dynamic Programming?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> A problem can be solved using Dynamic Programming if it contains some <strong>Optimal Substructure<\/strong> and <strong>Overlapping Subproblems.<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a rod of length n \u00a0and array prices of length n denoting the cost of&hellip;\n","protected":false},"author":5,"featured_media":3661,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[563],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3616"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3616"}],"version-history":[{"count":6,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3616\/revisions"}],"predecessor-version":[{"id":21896,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3616\/revisions\/21896"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3661"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3616"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3616"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3616"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}