Chapter 10DSA (Data Structures & Algorithms)~1 min read
Dynamic Programming
Complex Problems Efficiently Solve करा
Dynamic Programming (DP) म्हणजे complex problems ला overlapping subproblems मध्ये तोडणे आणि results cache (memoize) करणे. DP problems interview मध्ये hard म्हणून येतात — pattern शिकलं की solve होतात.
Marathi Analogy
DP म्हणजे smart student — एकच calculation दोनदा नाही करायची. Fibonacci(5) calculate केला आहे? तो लक्षात ठेव! Fibonacci(6) लागला तर Fibonacci(5) परत calculate नाही — memory मधून घे!
Fibonacci — Tabulation (Bottom-up DP)
python
def fib_dp(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(fib_dp(10)) # 55
# Time: O(n), Space: O(n)
# Space optimize करा — फक्त 2 variables
def fib_optimized(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
# Space: O(1)!Climbing Stairs — classic DP problem
python
# Problem: n stairs आहेत, एकावेळी 1 किंवा 2 steps चढता येतात
# किती ways आहेत n stairs चढायला?
def climb_stairs(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1 # 1 way: [1]
dp[2] = 2 # 2 ways: [1,1] or [2]
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2] # Fibonacci!
return dp[n]
print(climb_stairs(5)) # 8
# n=1:1, n=2:2, n=3:3, n=4:5, n=5:8- ▸DP identify करा: overlapping subproblems + optimal substructure
- ▸Memoization (Top-down): recursion + cache
- ▸Tabulation (Bottom-up): iterative + table
- ▸Classic problems: Fibonacci, Climbing Stairs, Coin Change, Longest Common Subsequence, 0/1 Knapsack
- ▸LeetCode DP problems: Easy → Medium → Hard order follow करा
✅ Key Points — लक्षात ठेवा
- ▸DP = recursion + memoization
- ▸Identify overlapping subproblems
- ▸Top-down: recursion + memo dict
- ▸Bottom-up: iterative dp array
- ▸State transition equation शोधणे key step
0/10 chapters पूर्ण