Week 03 - Dynamic Programming

Reference extracted from the detailed guide.

Watch First (CRITICAL - spend 2 hours here):

• NeetCode DP playlist: https://www.youtube.com/watch?v=mBNrRy2_hVs&list=PLot-Xpze53lcvx_tjrr_m2lgD2NsRHlNO
• Abdul Bari DP: https://www.youtube.com/watch?v=5dRGRueKU3M

DP Learning Method:

1. Identify if it's DP (optimal substructure + overlapping subproblems)
2. Define state: dp[i] = what does this represent?
3. Find recurrence: dp[i] = f(dp[i-1], dp[i-2], ...)
4. Determine base cases
5. Determine traversal order
6. Optimize space if possible

Day 1-2: 1D Dynamic Programming

Template: 1D DP

# House Robber Pattern
def rob(nums):
    if len(nums) <= 2:
        return max(nums) if nums else 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]

# Space optimized
def rob_optimized(nums):
    prev2, prev1 = 0, 0
    for num in nums:
        curr = max(prev1, prev2 + num)
        prev2 = prev1
        prev1 = curr
    return prev1

Day 3-4: 2D Dynamic Programming

Template: 2D DP

# Longest Common Subsequence
def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

# Edit Distance
def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j],    # delete
                                   dp[i][j-1],    # insert
                                   dp[i-1][j-1])  # replace
    
    return dp[m][n]

Day 5-6: Classic DP Problems

Template: Knapsack

# 0/1 Knapsack (Partition Equal Subset Sum)
def canPartition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in nums:
        for j in range(target, num - 1, -1):  # reverse!
            dp[j] = dp[j] or dp[j - num]
    
    return dp[target]

# Unbounded Knapsack (Coin Change)
def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for coin in coins:
        for j in range(coin, amount + 1):  # forward!
            dp[j] = min(dp[j], dp[j - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

Day 7: DP Review + Hard Problems

---