Register

GO Classes DPP | Algorithm|DP

323 views
3 3 votes

You are given a rod of length $n$ and an array prices where prices[i] is the selling price of a piece of length i . A fixed cost c is incurred for every cut made. Let $P[i]$ be the maximum profit from a rod of length $i$. Which of the following descriptions accurately represents the calculation for $P[i]$ ? (Assume $P[0]=0$ ).

  1. $P[i]=\max _{1 \leq j \leq i}(\operatorname{prices}[j]+P[i-j]-c)$
     
  2. $P[i]=\max \left(\operatorname{prices}[i], \max _{1 \leq j<i}(P[j]+P[i-j]-c)\right)$
     
  3. $P[i]=\max \left(\operatorname{prices}[i]-c, \max _{1 \leq j<i}(P[j]+P[i-j])\right)$
     
  4. $P[i]=\left(\max _{1 \leq j \leq i}(\operatorname{prices}[j]+P[i-j])\right)-c$

1 Answer

1 1 vote

The problem is rod-cutting with a cut cost of c.
Key points:

  • If we cut a rod of length $i$ into two pieces of lengths $j$ and $i-j$,
  • we earn prices[j] + P[i-j]
  • but we pay c once for that cut.
  • We also have the option of not cutting at all, selling the rod whole for prices[i], which incurs no cost.

The correct recurrence must therefore take the maximum of:

  • selling whole: prices[i]
  • best first-cut: prices[j] + P[i-j] - c for some $1 \leq j<i$.

Among the choices:
(B)

$$
P[i]=\max \left(\operatorname{prices}[i], \max _{1 \leq j<i}\{P[j]+P[i-j]-c\}\right)
$$


This exactly matches the reasoning above.

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | Alg...Next → · GO Classes DPP | Alg...
← Previous in category · GO Classes DPP | Alg...Next in category → · GO Classes DPP | Alg...
Position:
Show:

Related questions

2 2 votes
2 2 answers
404
404 views
GO Classes asked Sep 20, 2025
404 views
GO Classes DPP | Algorithm|SEARCH SPACE
You are given a sorted array of $n$ locations on a highway where charging stations are present. You need to select $k$ of these locations to install new fast chargers. Th...
4 4 votes
2 2 answers
425
425 views
GO Classes asked Sep 20, 2025
425 views
GO Classes DPP | Algorithm|BST
A Perfectly balanced binary search tree (BST) contains 15 distinct integers.The largest element is stored at the rightmost node of the tree.Which of the following element...
1 1 vote
1 1 answer
397
397 views
GO Classes asked Sep 20, 2025
397 views
GO Classes DPP | Algorithm|GREEDY
Consider a scheduling problem with $n$ tasks and $k$ distinct resources. Each task $i$ is represented by a tuple ( $s_{-} i, f_{-} i, r_{-} i$ ), where $s_{-} i$ is the s...
2 2 votes
1 1 answer
438
438 views
GO Classes asked Sep 20, 2025
438 views
GO Classes DPP | Algorithm|RECURRENCE RELATION
The time complexity of a recursive algorithm is given by the recurrence relation:$$\begin{aligned}& T(n)=\sqrt{n} T(\sqrt{n})+n \\& T(n)=1 \text { for } n \leq 2\end{alig...