Questions Tagged With dynamic-programminghttps://discuss.codechef.com/tags/dynamic-programming/?type=rss&user=h1ashdr%40gonquestions tagged <span class="tag">dynamic-programming</span>enWed, 24 Dec 2014 13:41:07 +0530Rod cutting dp problem[closed]https://discuss.codechef.com/questions/59729/rod-cutting-dp-problemclosed<p>I went through the explanation on lectures and the code given by geeksforgeeks and I have a little doubt in this line :</p>
<blockquote>
<p>max_val = max(max_val, price[j] +
val[i-j-1]);</p>
</blockquote>
<p>In this piece of code:</p>
<pre><code> /* Returns the best obtainable price for a rod of length n and
price[] as prices of different pieces */
int cutRod(int price[], int n)
{
int val[n+1];
val[0] = 0;
int i, j;
// Build the table val[] in bottom up manner and return the last entry
// from the table
for (i = 1; i<=n; i++)
{
int max_val = INT_MIN;
for (j = 0; j < i; j++)
max_val = max(max_val, price[j] + val[i-j-1]);
val[i] = max_val;
}
return val[n];
}
</code></pre>
<p>What I understood from the solution was that we take price of one piece and take the best of what else is left. For example :
If the length of rod is 4 then we should take max of (Price of not cutting at all,that is taking the rod of 4 as it is to get the maximum revenue, (Price of 1 ,best of 3 || Price of 2,best of 2,etc..))</p>
<p>So according to me the code should be :
max_val = max(Price of ith piece,Price[j]+val[i-j-1]) or something like that.</p>h1ashdr@gonWed, 24 Dec 2014 13:41:07 +0530https://discuss.codechef.com/questions/59729/rod-cutting-dp-problemcloseddynamic-programmingproblemcuttingrod