DP example
jagadeesha
September 2025
1 Example
Lets see (‘n=4‘, prices ‘p[1]=1, p[2]=5, p[3]=8, p[4]=9‘) using both Memoiza-
tion and Bottom-up .
1. Top-Down with Memoization
We call ‘solve(4)‘.
Step 1 – Start at ‘n=4‘
Try cut length ‘1‘: revenue = ‘p[1] + solve(3)‘ = ‘1 + ?
Try cut length ‘2‘: revenue = ‘p[2] + solve(2)‘ = ‘5 + ?
Try cut length ‘3‘: revenue = ‘p[3] + solve(1)‘ = ‘8 + ?
Try cut length ‘4‘: revenue = ‘p[4] + solve(0)‘ = ‘9 + 0 = 9
‘
We now need to compute ‘solve(3)‘, ‘solve(2)‘, and ‘solve(1)‘.
Step 2 – Solve(3)
Cut ‘1‘: ‘p[1] + solve(2)‘ = ‘1 + ?
Cut ‘2‘: ‘p[2] + solve(1)‘ = ‘5 + ?
Cut ‘3‘: ‘p[3] + solve(0)‘ = ‘8 + 0 = 8‘
So we need ‘solve(2)‘ and ‘solve(1)‘.
Step 3 – Solve(2)
Cut ‘1‘: ‘p[1] + solve(1)‘ = ‘1 + ?
Cut ‘2‘: ‘p[2] + solve(0)‘ = ‘5 + 0 = 5‘
Need ‘solve(1)‘.
Step 4 – Solve(1)
1
Cut ‘1‘: ‘p[1] + solve(0)‘ = ‘1 + 0 = 1‘.
So ‘solve(1) = 1‘. (memoize it)
Back to ‘solve(2)‘:
Option ‘1+solve(1)‘ = ‘1+1 = 2‘
Option ‘2+solve(0)‘ = ‘5‘
So ‘solve(2) = 5‘. (memoize)
Back to ‘solve(3)‘:
Cut 1: ‘1+solve(2)‘ = ‘1+5 = 6‘
Cut 2: ‘5+solve(1)‘ = ‘5+1 = 6‘
Cut 3: ‘8‘
So ‘solve(3) = 8‘. (memoize)
Back to ‘solve(4)‘:
Cut 1: ‘1+solve(3)‘ = ‘1+8 = 9‘
Cut 2: ‘5+solve(2)‘ = ‘5+5 = 10‘ : best !
Cut 3: ‘8+solve(1)‘ = ‘8+1 = 9‘
Cut 4: ‘9‘
So ‘solve(4) = 10‘. (memoize)
Final answer (memoization):
Maximum revenue = 10
Optimal cuts = ‘[2,2]‘
— —-
2. Bottom-Up (Tabulation)
We fill a ‘dp‘ array from ‘0‘ to ‘4‘.
‘dp[0] = 0‘
Compute dp [1]
Cut 1: ‘p[1] + dp[0] = 1 + 0 = 1‘
So ‘dp[1] = 1‘.
Compute dp [2]
2
Cut 1: ‘p[1] + dp[1] = 1 + 1 = 2‘
Cut 2: ‘p[2] + dp[0] = 5 + 0 = 5‘ ; good
So ‘dp[2] = 5‘.
Compute dp [3]
Cut 1: ‘p[1] + dp[2] = 1 + 5 = 6‘
Cut 2: ‘p[2] + dp[1] = 5 + 1 = 6‘
Cut 3: ‘p[3] + dp[0] = 8 + 0 = 8‘ ; good
So ‘dp[3] = 8‘.
Compute dp [4]
Cut 1: ‘p[1] + dp[3] = 1 + 8 = 9‘
Cut 2: ‘p[2] + dp[2] = 5 + 5 = 10‘ ; good
Cut 3: ‘p[3] + dp[1] = 8 + 1 = 9‘
Cut 4: ‘p[4] + dp[0] = 9 + 0 = 9‘
So ‘dp[4] = 10‘.
Final answer (bottom-up):
Maximum revenue = 10 Optimal cuts = ‘[2,2]‘
—
Memoization: Recursive, solves only needed subproblems. It started from
‘n=4‘ and broke downwards, caching ‘solve(1)=1‘, ‘solve(2)=5‘, ‘solve(3)=8‘,
then used them to compute ‘solve(4)=10‘.
Bottom-Up: Iterative, fills the table from ‘0 → n‘. It explicitly computed all
‘dp[k]‘ for ‘k=1..4‘ in order, ensuring each step builds on smaller ones.
Both give the same final result: Revenue = 10, Cuts = [2,2].
—