DP 24. Rod Cutting Problem | 1D Array Space Optimised Approach

This chapter marks the culmination of the Dynamic Programming on Subsequences series. We examine the classic Rod Cutting Problem, mapping it directly to the Unbounded Knapsack pattern, and systematically evolve our solution from raw recursion through memoization, tabulation, 2-row space optimization, and finally to an optimal 1D array space-optimized implementation.

1. Problem Statement & The Core Paradigm Shift

Problem Definition

Given a rod of total length $n$ and an array of prices where price[i] represents the market value of a rod of length i + 1, determine the maximum total value obtainable by cutting the rod into smaller pieces and selling them.

Example Input:

• Rod Length ($n$): 5
• Price Array: [2, 5, 7, 8, 10]
  • Length 1 price = 2
  • Length 2 price = 5
  • Length 3 price = 7
  • Length 4 price = 8
  • Length 5 price = 10

Real-Life Analogy: The Unbounded Knapsack Reframe

Mental Hook: Beginners often get confused by thinking about how to break a single rod of length $n$ into pieces. Instead, invert the perspective: Think of collecting rod lengths from an infinite supply to sum up to target $n$, while maximizing the accumulated price.

This inverse perspective transforms the cutting problem into the Unbounded Knapsack Problem, where:

• Available Items: Rod lengths corresponding to indices plus one (rod_length = index + 1).
• Item Values: Market prices (price[index]).
• Capacity: The target rod length $n$.
• Supply: Infinite (you can pick the same rod length multiple times).

2. Exhaustive Step-by-Step Solution Evolution

To master this problem, we follow the standard dynamic programming progression:

1. Recursive Brute Force (Exponential time, exponential auxiliary stack space)
2. Memoization / Top-Down DP ($O(N \times N)$ time, $O(N \times N) + \text{Stack}$ space)
3. Tabulation / Bottom-Up DP ($O(N \times N)$ time, $O(N \times N)$ space)
4. 2-Array Space Optimization ($O(N \times N)$ time, $O(N)$ space)
5. 1D Array Space Optimization ($O(N \times N)$ time, $O(N)$ space with single-array in-place updates)

3. Recursive Formulation & Recurrence Relations

We define our recursive function f(index, target_n) which evaluates the maximum price obtainable considering rod lengths from index 0 up to index, in order to form a total target length target_n.

Choices at Each Step:

1. Not-Take: Skip the current rod length. Value added is 0, and we move to the previous index:

2. Take: If the current rod length (index + 1) is less than or equal to target_n, we can pick it. Because we have an infinite supply, we stay at the same index and reduce our target:

We take the maximum of these two choices:

Base Case Analysis

When index == 0, our available rod length is 1 (index + 1 = 1). To form any remaining target length target_n, we must use target_n pieces of length 1.

4. Recursion and Memoization (Top-Down Approach)

To eliminate overlapping subproblems, we introduce a memoization table dp[index][n] initialized to -1.

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
private:
    int solveMemo(int ind, int n, vector<int>& price, vector<vector<int>>& dp) {
        // Base Case: At index 0, we can only form length 'n' using n rods of length 1
        if (ind == 0) {
            return n * price[0];
        }
        
        if (dp[ind][n] != -1) return dp[ind][n];
        
        // Not-Take case
        int notTake = solveMemo(ind - 1, n, price, dp);
        
        // Take case (only if rod length <= remaining target n)
        int take = -1e9;
        int rodLength = ind + 1;
        if (rodLength <= n) {
            // Stay at the same index because of infinite supply
            take = price[ind] + solveMemo(ind, n - rodLength, price, dp);
        }
        
        return dp[ind][n] = max(notTake, take);
    }

public:
    int cutRod(vector<int>& price, int n) {
        vector<vector<int>> dp(n, vector<int>(n + 1, -1));
        return solveMemo(n - 1, n, price, dp);
    }
};

5. Tabulation (Bottom-Up Approach)

In tabulation, we convert the top-down logic into an iterative bottom-up structure:

• Base Case Translation: Fill row 0 for all possible targets n from 0 to N using n * price[0].
• Nested Loops: Outer loop iterates over index from 1 to N - 1. Inner loop iterates over target n from 0 to N.

class Solution {
public:
    int cutRod(vector<int>& price, int n) {
        vector<vector<int>> dp(n, vector<int>(n + 1, 0));
        
        // Base Case initialization for index 0
        for (int target = 0; target <= n; target++) {
            dp[0][target] = target * price[0];
        }
        
        // Fill table bottom-up
        for (int ind = 1; ind < n; ind++) {
            for (int target = 0; target <= n; target++) {
                int notTake = dp[ind - 1][target];
                
                int take = -1e9;
                int rodLength = ind + 1;
                if (rodLength <= target) {
                    // Notice we use dp[ind][target - rodLength] (same row) for unbounded supply
                    take = price[ind] + dp[ind][target - rodLength];
                }
                
                dp[ind][target] = max(notTake, take);
            }
        }
        
        return dp[n - 1][n];
    }
};

6. Space Optimization: 2-Array to 1D Array

Understanding State Dependency

When computing the current row (curr), we only require:

1. Values from the strictly above row (previous[target]) for the notTake option.
2. Values from the current row at a smaller target (curr[target - rodLength]) for the take option (because of infinite supply).

Because values to the left in the same row are already updated with current-row calculations, we do not need a separate 2D grid or even two separate vectors (prev and curr). We can compress everything down into a single 1D array.

1D Array Space-Optimized Implementation

class Solution {
public:
    int cutRod(vector<int>& price, int n) {
        // Single 1D dp array of size n + 1
        vector<int> dp(n + 1, 0);
        
        // Base Case initialization for index 0
        for (int target = 0; target <= n; target++) {
            dp[target] = target * price[0];
        }
        
        // Iterate over all rod lengths (indices 1 to n - 1)
        for (int ind = 1; ind < n; ind++) {
            for (int target = 0; target <= n; target++) {
                int notTake = dp[target]; // Comes from the "above" row
                
                int take = -1e9;
                int rodLength = ind + 1;
                if (rodLength <= target) {
                    // Comes from the "current" row (left side of the array)
                    take = price[ind] + dp[target - rodLength];
                }
                
                dp[target] = max(notTake, take);
            }
        }
        
        return dp[n];
    }
};

7. Complexity Analysis Summary

Summary and Key Takeaways

• Problem Inversion: Framing rod cutting as collecting rod lengths to sum up to target $n$ converts a complex partitioning problem into the standard Unbounded Knapsack pattern.
• Infinite Supply Rule: Whenever items can be picked infinitely, we evaluate take by staying at the same index (ind), querying the already-computed values from the current state.
• Base Case Precision: At index 0, the rod length is 1, meaning a target length $n$ requires exactly $n$ pieces of length 1, yielding a base price of $n \times \text{price}[0]$.
• Transitioning to 1D: Because the recurrence relies only on the previous row (notTake) and the current row's left cells (take), 2D space can be compressed into a single 1D vector updated sequentially from left to right.
• Series Completion: This lecture successfully concludes the Dynamic Programming on Subsequences series, establishing a robust foundation for solving subset, knapsack, and partitioning variations across coding interviews.