DSA

Rod Cutting

Covers: Memoized, tabulation. Optimal — Time O(n x n), Space O(n).

August 8, 2026
DSADynamic ProgrammingDPLeetCodePractice

Practice Link

Given a rod of length n(size of price) inches and an array of prices, price. price[i] denotes the value of a piece of length i. Determine the maximum value obtainable by cutting up the rod and selling the pieces.

Memoized Approach#

This is an unbounded knapsack variant: the rod can be cut into pieces of the same length repeatedly. The state (idx, n) represents the maximum value obtainable using piece lengths 0..idx from a rod of remaining length n. At each length, either skip it (move to idx-1) or cut a piece of that length (add its price and stay at the same idx for future cuts). The base case uses only length-1 pieces: n * price[0]. Caching memo[idx][n] reduces the overlapping recomputation to O(n^2) states.

cpp
class Solution {
  public:
  
  int solve(int idx,int n, vector<int> &price, vector<vector<int>> &memo)
    {
        if(idx==0)
            return n * price[0];
        if(memo[idx][n]!= -1)
            return memo[idx][n];
            
        int notTake = solve(idx-1, n, price, memo);
        
        int take = INT_MIN;
        int rodLength = idx+1;
        if(rodLength <= n)
            take = price[idx] + solve(idx, n-rodLength, price, memo);
            
        return memo[idx][n] = max(take, notTake);
    }
  
    int cutRod(vector<int> &price) {
        int n = price.size();
       vector<vector<int>> memo(n, vector<int>(n+1, -1));
        return solve(n-1, n, price, memo);
    }
};

Time Complexity: O(n x n)

Space Complexity: O(n x n) + O(n)

Tabulation Approach#

Build the table bottom-up. Initialize the first row with dp[0][j] = j * price[0] (using only length-1 pieces). For each subsequent length i and remaining rod length j, combine "not take" (from the row above) and "take" (unbounded — reads from the current row dp[i][j - rodLength]). This iterative fill removes the recursion stack while keeping O(n^2) time and space.

cpp
class Solution {
  public:
    int cutRod(vector<int> &price) {
        int n = price.size();
        vector<vector<int>> dp(n, vector<int>(n+1, 0));
        
        for(int j=0;j<=n;j++)
        {
            dp[0][j] = j*price[0];
        }
       
       for(int i=1;i<n;i++)
       {
           for(int j=0;j<=n;j++)
           {
               int notTake = dp[i-1][j];
        
                int take = INT_MIN;
                int rodLength = i+1;
                
                if(rodLength <= j)
                    take = price[i] + dp[i][j-rodLength];
                
                
                dp[i][j] = max(take, notTake);
           }
       }
       
       
        return dp[n-1][n];
    }
};

Time Complexity: O(n x n)

Space Complexity: O(n x n)

Space Optimized Solution#

Each row dp[i] reads from dp[i-1] (the previous row) for "not take" and from curr itself (the current row) for "take" (because the cut can be reused). We maintain two 1D arrays (prev and curr) and swap after each row. Space drops from O(n^2) to O(n) with the same O(n^2) time.

cpp
class Solution {
  public:
    int cutRod(vector<int> &price) {
        int n = price.size();
        vector<int> prev(n+1, 0), curr(n+1,0);
        
        for(int j=0;j<=n;j++)
        {
            prev[j] = j*price[0];
        }
       
       for(int i=1;i<n;i++)
       {
           for(int j=0;j<=n;j++)
           {
               int notTake = prev[j];
        
                int take = INT_MIN;
                int rodLength = i+1;
                
                if(rodLength <= j)
                    take = price[i] + curr[j-rodLength];
                
                
                curr[j] = max(take, notTake);
           }
           prev = curr;
       }
       
        return prev[n];
    }
};

Time Complexity: O(n x n)

Space Complexity: O(n)

Related articles

DSALongest Common Prefix5 approaches incl. Horizontal Scanning, Vertical Scanning, Binary Search, and more. Optimal — Time O(s log m), Space O(1).DSAMaximum Subarray SumCovers: Brute Force, Optimal. Optimal — Time O(n), Space O(1).DSAPalindromic SubstringCovers: Brute Force: generate all su…, Expansion on center, DP. Optimal — Time O(n<sup>2</sup>), Space O(n<sup>2</sup>).