41: 1+8=9, 2: 5+5=10, 3: 8+1=9, 4:9+0=9102Two pieces of length 251:1+10=11, 2:5+8=13, 3:8+5=13, 4:9+1=10, 5:10+0=10132First achieving 13 is cut=261:1+13=14, 2:5+10=15, 3:8+8=16, 4:9+5=14, 5:10+1=11, 6:17+0=17176Single length 6 piece71:1+17=18, 2:5+13=18, 3:8+10=18, 4:9+8=17, 5:10+5=15, 6:17+1=18, 7:17+0=17181First 18 encountered at i=181:1+18=19, 2:5+17=22, 3:8+13=21, 4:9+10=19, 5:10+8=18, 6:17+5=22, 7:17+1=18, 8:20+0=20222First 22 encountered at i=2

Reconstruction for n = 8:

firstCut[8] = 2  -> remaining 6
firstCut[6] = 6  -> remaining 0
Cuts sequence: [2, 6]  (order of discovery; can also report sorted)
Revenue = dp[8] = 22 ( = price[2-1] + price[6-1] = 5 + 17 )

Key observations:

Multiple first cuts can yield the same best value (e.g., L = 7); we keep the first encountered for deterministic reconstruction.
The 1D DP reuses smaller solved lengths directly (dp[L-i]).
This progression matches the recurrence: dp[L] = max_{1..L} ( price[i-1] + dp[L-i] ).

Method 4 - Bottom-Up 2D DP (Knapsack Style Variant)

Intuition

We can view each piece length i as an item usable multiple times (unbounded knapsack). A 2D table dp[i][L] = best revenue using piece lengths up to i to fill total length

Related Tags

Continue Practicing