Overview
Coin change: minimum coins se target amount banao — DP ka must-know problem hai yaar.
Analogy
Jaise ATM se minimum notes mein amount nikalna — smaller denominations bhi consider karo.
Step-by-step
- dp[i] = minimum coins se amount i
- dp[0] = 0 (base case)
- Har amount ke liye sab coins try karo: dp[i] = min(dp[i], dp[i-coin]+1)
- dp[amount] answer hai (ya infinity agar impossible)
Visual
coins=[1,3,4], amount=6
dp[0]=0
dp[1]=1 (coin 1)
dp[3]=1 (coin 3)
dp[4]=1 (coin 4)
dp[6]=2 (3+3)
Common mistakes
- dp initialization: infinity ya amount+1 use karo
- Greedy coin change sirf special cases mein optimal
- Coin reuse allowed — unbounded knapsack hai ye
Practice questions
- Coin change minimum coins solve karo
- Coin change II: count ways to make amount solve karo