Rod Cutting — Maximize Revenue from Segments

Recurrence

dp[n] = max over i in 1..n of (p[i] + dp[n - i]).

Implementation

int rodCutting(int[] price, int n) {
  int[] dp = new int[n + 1];
  for (int len = 1; len <= n; len++)
    for (int cut = 1; cut <= len; cut++)
      dp[len] = Math.max(dp[len], price[cut] + dp[len - cut]);
  return dp[n];
}

Reconstruction

Store argmax at each length. Trace back cuts from dp[n].

Applications

Cloth cutting. Metal sheet slicing. Any 'break large into optimal small pieces' problem.