Q4Design and Analysis of Algorithms

Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler, overlapping subproblems and storing the results to avoid redundant computation. It applies when the problem has:

• Overlapping Subproblems: Same subproblems are solved multiple times (unlike Divide & Conquer).
• Optimal Substructure: Optimal solution is composed of optimal solutions to subproblems.
• Two implementation styles: Top-Down (Memoization) — recursive + cache; Bottom-Up (Tabulation) — iterative table filling.

Items: (v=6,w=2), (v=10,w=4), (v=12,w=6). Capacity W=10. Build dp[i][w] table (i = items 0 to 3, w = capacity 0 to 10).

• dp[0][w] = 0 for all w (no items → no value).
• Item 1 (v=6,w=2): dp[1][w] = 6 for w≥2, else 0.
• Item 2 (v=10,w=4): dp[2][w] = max(dp[1][w], 10+dp[1][w-4]). dp[2][4]=10, dp[2][6]=16 (6+10).
• Item 3 (v=12,w=6): dp[3][10] = max(dp[2][10], 12+dp[2][4]) = max(16, 22) = 22.
• Optimal: Take items 1 (w=2,v=6) and 3 (w=6,v=12) and item 2 (w=4,v=10) but 2+6+4>10. Take items 2+3: 4+6=10, v=22. ✓

Given coins of denominations {1, 3, 4} and target amount = 6, find the minimum number of coins to make the amount.

DP Formulation: dp[0] = 0. For w from 1 to 6: dp[w] = min over all coins c where c ≤ w of { dp[w-c] + 1 }.

• dp[0] = 0
• dp[1] = min(dp[0]+1) = 1 (coin 1)
• dp[2] = min(dp[1]+1) = 2 (1+1)
• dp[3] = min(dp[2]+1, dp[0]+1) = 1 (coin 3)
• dp[4] = min(dp[3]+1, dp[1]+1, dp[0]+1) = 1 (coin 4)
• dp[5] = min(dp[4]+1, dp[2]+1, dp[1]+1) = 2 (4+1)
• dp[6] = min(dp[5]+1, dp[3]+1, dp[2]+1) = 2 (3+3)

Minimum coins for 6 = 2 (using coins {3, 3}). Time Complexity: O(amount × number_of_coins). Space: O(amount). This is the classic unbounded version where each coin can be used multiple times.