Given a rod of length N inches and an array of prices, price[]. price[i] denotes the value of a piece of length i. Determine the maximum value you can obtain by cutting up the whole rod and selling the pieces.
Note: Consider 1-based indexing.
N = 8
Price[] = {1, 5, 8, 9, 10, 17, 17, 20}
Output: 22
Explanation: The maximum obtainable value is 22 by cutting in two pieces of lengths 2 and 6, i.e., 5+17=22.
Similiar To Unbounded Knapsack : https://leetcode.com/discuss/interview-question/4860416/unbounded-knapsack-top-downbottom-up-4-solutions-self-explanatory-c-code
Approach 1 : Using Top Down DP (Recursion To Memoization)
class TopDown {
int n;
// O(2^(N+N)) & O(N+N)
int solveWithoutMemo(const vector<int>& price, int cutLen, int rodLen) {
if(rodLen == 0 || cutLen > n)
return 0;
int skipCut = solveWithoutMemo(price, cutLen + 1, rodLen);
int performCut = cutLen <= rodLen
? price[cutLen - 1] + solveWithoutMemo(price, cutLen, rodLen - cutLen)
: 0;
return max(performCut, skipCut);
}
// O(N^2) & O(N^2)
int solveWithMemo(vector<vector<int>>& memory, const vector<int>& price, int cutLen, int rodLen) {
if(cutLen > n || rodLen == 0)
return 0;
if(memory[cutLen][rodLen] != -1)
return memory[cutLen][rodLen];
int skipCut = solveWithMemo(memory, price, cutLen + 1, rodLen);
int performCut = cutLen <= rodLen
? price[cutLen - 1] + solveWithMemo(memory, price, cutLen, rodLen - cutLen)
: 0;
return memory[cutLen][rodLen] = max(performCut, skipCut);
}
// O(N^3) & O(N^2)
int solveWithMemoLoop(vector<vector<int>>& memory, const vector<int>& price, int start, int rodLen) {
if(start > n || rodLen == 0)
return 0;
if(memory[start][rodLen] != -1)
return memory[start][rodLen];
int maxValue = 0;
for(int cutLen = start; cutLen <= n; ++cutLen) {
int performCut = cutLen <= rodLen
? price[cutLen - 1] + solveWithMemoLoop(memory, price, cutLen, rodLen - cutLen)
: 0;
maxValue = max(maxValue, performCut);
}
return memory[start][rodLen] = maxValue;
}
public:
int cutRod(vector<int>& price) {
n = price.size();
vector<vector<int>> memory(n + 1, vector<int>(n + 1, -1));
return solveWithMemo(memory, price, 1, n);
}
};Approach 2 : Using Bottom Up DP (2D + 1D Tabulation)
class BottomUp {
int n;
// O(N^2) & O(N^2)
int solveBy2DTable(const vector<int>& price) {
vector<vector<int>> dp(n + 2, vector<int>(n + 1, 0));
for(int cutLen = n; cutLen >= 1; --cutLen) {
for(int rodLen = 1; rodLen <= n; ++rodLen) {
int skipCut = dp[cutLen + 1][rodLen];
int performCut = cutLen <= rodLen
? price[cutLen - 1] + dp[cutLen][rodLen - cutLen]
: 0;
dp[cutLen][rodLen] = max(performCut, skipCut);
}
}
return dp[1][n];
}
// O(N^2) & O(N)
int solveBy1DTable(const vector<int>& price) {
vector<int> nextRow(n + 1, 0), currRow(n + 1, 0);
for(int cutLen = n; cutLen >= 1; --cutLen) {
for(int rodLen = 1; rodLen <= n; ++rodLen) {
int skipCut = nextRow[rodLen];
int performCut = cutLen <= rodLen
? price[cutLen - 1] + currRow[rodLen - cutLen]
: 0;
currRow[rodLen] = max(performCut, skipCut);
}
swap(nextRow, currRow);
}
return nextRow[n];
}
public:
int cutRod(vector<int>& price) {
n = price.size();
return solveBy1DTable(price);
}
};𝗨𝗣𝗩𝗢𝗧𝗘 𝗜𝗙 𝗬𝗢𝗨 𝗟𝗜𝗞𝗘 𝗧𝗛𝗘 𝗦𝗢𝗟𝗨𝗧𝗜𝗢𝗡 👍
Note: This solutions are created by myself :)