Lesson 1 � Beginner

DP: Recursion se Memoization tak

Dynamic Programming (DP) recursion ka optimization hai. Jab recursion mein same subproblems baar baar solve hote hain � overlapping subproblems � toh hum unko store karke dubara use karte hain. DP do cheezein require karta hai: overlapping subproblems aur optimal substructure. Is lesson mein hum recursion tree se shuru karke memoization aur tabulation tak jaayenge.

DP kya hai?

Overlapping Subproblems kya hoti hain?

Fibonacci example lo. Recursion mein fib(5) ke liye tum fib(3) do baar compute karte ho � ye overlapping subproblem hai:

# Recursion Tree � fib(5) mein SAME calls baar baar aa rahe hain
#
# fib(5)
# / \
# fib(4) fib(3)
# / \ / \
# fib(3) fib(2) fib(2) fib(1)
# / \ / \ / \
# fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
# / \
# fib(1) fib(0)
#
# fib(3) = 2 baar, fib(2) = 3 baar, fib(1) = 5 baar
# Ye sab overlapping subproblems hain � time O(2^n)!

Memoization (Top-Down DP)

Memoization matlab recursion ke saath jaao aur har result ko dictionary/list mein store karo. Dobara wahi subproblem aaye toh stored value se utha lo:

# Memoization � Top-Down DP
def fib(n, memo={}):
 if n in memo:
 return memo[n] # Already computed hai!
 if n <= 1:
 return n
 memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
 return memo[n]

# fib(5) ab O(n) mein hota hai!
print(fib(5)) # 5
print(fib(50)) # 12586269025 � turant!

Tabulation (Bottom-Up DP)

Tabulation mein recursion nahi hota � seedha chhote se bade subproblem ki taraf jaate hain. DP table fill karte hain bottom-up:

# Tabulation � Bottom-Up DP
def fib(n):
 if n <= 1:
 return n
 dp = [0] * (n + 1)
 dp[0] = 0
 dp[1] = 1
 for i in range(2, n + 1):
 dp[i] = dp[i - 1] + dp[i - 2]
 return dp[n]

print(fib(5)) # 5
print(fib(50)) # 12586269025

DP Table Fill Visualization

Fibonacci ka DP table dekho � kaise har cell fill hoti hai:

# DP Table: dp[i] = dp[i-1] + dp[i-2]
#
# Index: 0 1 2 3 4 5
# Value: 0 1 1 2 3 5
# ? ? ? ? ? ?
# base base 0+1 1+1 1+2 2+3
#
# Har step mein:
# dp[2] = dp[1] + dp[0] = 1 + 0 = 1
# dp[3] = dp[2] + dp[1] = 1 + 1 = 2
# dp[4] = dp[3] + dp[2] = 2 + 1 = 3
# dp[5] = dp[4] + dp[3] = 3 + 2 = 5

Memoization vs Tabulation

Space Optimization

DP table mein agar sirf last 2 values se current value banti hai toh pura table rakhne ki zaroorat nahi � sirf 2 variables rakh lo:

# Space Optimized Fibonacci � O(1) space!
def fib(n):
 if n <= 1:
 return n
 prev2 = 0 # dp[i-2]
 prev1 = 1 # dp[i-1]
 for i in range(2, n + 1):
 curr = prev1 + prev2
 prev2 = prev1
 prev1 = curr
 return prev1

# Time: O(n), Space: O(1) � best possible!

Try it: code khud likho

Exercise

Common mistakes

• Memo dictionary initialize karna bhool jaana: Default argument memo={} sirf ek baar initialize hota hai. Agar function doosri baar call ho toh purana cache rehta hai � careful raho. Better hai None default rakhke andar initialize karo.
• Base case galat hona: Fibonacci mein n <= 1 return n karo. Agar base case miss ho gaya toh infinite recursion hoga.
• Tabulation mein order galat hona: Bottom-up mein chhote subproblems pehle solve karo. Agar dp[i] ke liye dp[i-1] chahiye toh i=1 se shuru karo, i=0 nahi.
• Space optimization skip karna: Agar sirf last 1-2 values chahiye toh pura DP table mat banao � variables se kaam lo.
• DP aur recursion confusion: Memoization = recursion + cache. Tabulation = iterative + table. Dono ka result same hota hai, sirf approach alag hai.