Lesson 2 — Beginner

DP Patterns: Fibonacci se Knapsack tak

DP problems solve karne ka sabse easy tareeka hai pattern recognition. Agar tumhe 5-6 common patterns aate hain toh interview mein 80% DP problems pehchaan sakte ho. Is lesson mein hum Fibonacci, Climbing Stairs, House Robber, Coin Change, aur Grid Paths jaise patterns dekhenge. Har pattern ka template yaad karlo — problem aayegi toh seedha lagaa doge.

⏱ 30 min• Beginner• DP Basics

Pattern 1: Fibonacci Sequence

Sabse pehla aur sabse common pattern — har step pe pehle 2 values ka sum. Fibonacci, Climbing Stairs, House Robber — sab is pattern pe based hain:

# Fibonacci — har element = previous 2 ka sum
def fib(n):
 if n <= 1:
 return n
 dp = [0] * (n + 1)
 dp[0], dp[1] = 0, 1
 for i in range(2, n + 1):
 dp[i] = dp[i - 1] + dp[i - 2]
 return dp[n]

# Climbing Stairs — exactly same pattern!
# n stairs hain, 1 ya 2 steps le sakte ho
def climbStairs(n):
 if n <= 2:
 return n
 dp = [0] * (n + 1)
 dp[1], dp[2] = 1, 2
 for i in range(3, n + 1):
 dp[i] = dp[i - 1] + dp[i - 2]
 return dp[n]

Pattern Recognition: Agar problem mein "har step pe 1 ya 2 steps le sakte ho" ya "current = previous 2 ka function" jaisa kuch dikhe — toh ye Fibonacci pattern hai. DP relation: dp[i] = dp[i-1] + dp[i-2].

Pattern 2: House Robber

House Robber mein adjacent nahi le sakte — isliye "ya toh current lo ya previous lo" wala max lagta hai:

# House Robber — adjacent nahi le sakte
def rob(nums):
 if len(nums) == 1:
 return nums[0]
 dp = [0] * len(nums)
 dp[0] = nums[0]
 dp[1] = max(nums[0], nums[1])
 for i in range(2, len(nums)):
 dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
 return dp[-1]

# Pattern: dp[i] = max(include current, exclude current)
# include = dp[i-2] + nums[i]
# exclude = dp[i-1]

Pattern 3: Coin Change (Unbounded Knapsack)

Coins available hain, target amount hai — kitne minimum coins chahiye? Har coin ko baar baar use kar sakte ho:

# Coin Change — minimum coins to make amount
def coinChange(coins, amount):
 dp = [float('inf')] * (amount + 1)
 dp[0] = 0 # 0 coins se 0 amount banta hai
 for i in range(1, amount + 1):
 for coin in coins:
 if coin <= i and dp[i - coin] != float('inf'):
 dp[i] = min(dp[i], dp[i - coin] + 1)
 return dp[amount] if dp[amount] != float('inf') else -1

# coins = [1, 5, 10, 25], amount = 30
# dp[30] = min coins to make 30 — answer: 2 (25+5)

Unbounded Knapsack Pattern: Jab same cheez baar baar use kar sakte ho (jaise coins unlimited hain), toh ye pattern lagta hai. Relation: dp[i] = min(dp[i], dp[i-coin] + 1) for each coin.

Pattern 4: Grid Paths

Grid mein top-left se bottom-right jaana hai — sirf right ya down ja sakte ho. Kitne unique paths hain?

# Unique Paths — m x n grid, sirf right/down
def uniquePaths(m, n):
 dp = [[1] * n for _ in range(m)]
 for i in range(1, m):
 for j in range(1, n):
 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
 return dp[m - 1][n - 1]

# Grid Visualization:
# 1 1 1 1 1
# 1 2 3 4 5
# 1 3 6 10 15
# 1 4 10 20 35
#
# dp[i][j] = dp[i-1][j] + dp[i][j-1]
# upar se aao + baayan se aao = total paths

Pattern 5: 0/1 Knapsack

Items hain, weight limit hai — maximum value le jaao. Har item ek baar le sakte ho ya chhod sakte ho:

# 0/1 Knapsack — har item ek baar
def knapsack(W, wt, val, n):
 dp = [[0] * (W + 1) for _ in range(n + 1)]
 for i in range(1, n + 1):
 for w in range(1, W + 1):
 if wt[i - 1] <= w:
 dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w])
 else:
 dp[i][w] = dp[i - 1][w]
 return dp[n][W]

# Pattern: ya item lo (val + remaining space) ya mat lo (purana max)
# dp[i][w] = max(include, exclude)

Pattern Recognition Chart

# Pattern Recognition Quick Reference:
#
# | Problem Type | Pattern | DP Relation |
# |---------------------------|------------------|--------------------------------|
# | Fibonacci / Climbing | Linear | dp[i] = dp[i-1] + dp[i-2] |
# | House Robber | Linear Max | dp[i] = max(dp[i-1], dp[i-2]+x)|
# | Coin Change | Unbounded Knapsack| dp[i] = min(dp[i], dp[i-coin]+1)|
# | Grid Paths | 2D Grid | dp[i][j] = up + left |
# | 0/1 Knapsack | 2D Selection | dp[i][w] = max(include, exclude)|
# | Subset Sum | 0/1 Selection | dp[i][s] = dp[i-1][s] || dp[i-1][s-arr[i]] |

Try it: code khud likho

Exercise

Question: Coins = [1, 5, 10] aur amount = 12 hai. Minimum kitne coins chahiye? Sirf number daalo.

Question: Jab problem mein adjacent elements nahi le sakte (jaise House Robber), toh ye konsa DP pattern hai? Sirf pattern ka naam daalo.

Common mistakes

Pattern pehchaan nahi hona: Har DP problem unique lagta hai but mostly 5-6 patterns repeat hote hain. Pattern chart yaad karo — problem aayi toh seedha matching pattern pe apply karo.
Base case miss karna: Fibonacci mein dp[0]=0, dp[1]=1. Climbing Stairs mein dp[1]=1, dp[2]=2. Har pattern ka apna base case hota hai — yaad karo.
Unbounded vs 0/1 confuse karna: Agar same item baar baar le sakte ho toh unbounded hai (Coin Change). Agar sirf ek baar hai toh 0/1 hai (Knapsack). Dono mein loop order alag hota hai.
Grid mein direction galat hona: Unique Paths mein sirf right aur down ja sakte ho. Upar ya left nahi ja sakte. DP table mein dp[i][j] = dp[i-1][j] + dp[i][j-1] — upar + baayan.
Space optimization skip karna: Fibonacci pattern mein sirf last 2 values chahiye — pura table mat banao. 2 variables se kaam lo.

Lesson complete?

DP patterns samajh aa gaya? Ab 0/1 Knapsack detail mein dekhte hain — sabse important DP pattern jo interview mein baar baar aata hai.