🧩 Dynamic Programming (Coding)

Day 4 | ⏱️ 3 Hours | TCS Interview Prep

📌 Subtopics

• Coin Change: Minimum coins to make a value, number of ways to make change
• Minimum Edit Distance: Convert one string to another with min operations (insert, delete, replace)
• Strategy: Recursion → Memoization (top-down) → Tabulation (bottom-up)
• 0/1 Knapsack pattern
• Fibonacci-based DP problems

🌐 Learning Resources

✅ Must-Practice Problems (LeetCode)

📝 Key Patterns

# Coin Change — Minimum Coins (Tabulation)
def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

# Edit Distance (Tabulation)
def edit_distance(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], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

# DP Strategy:
# 1. Define state: dp[i] = answer for subproblem of size i
# 2. Define transition: dp[i] = f(dp[i-1], dp[i-2], ...)
# 3. Base case: dp[0] = ...
# 4. Return: dp[n]

🔗 Related Topics

• Arrays and Hashing — Tabulation tables and memoization maps are stored in arrays and hash map structures
• Strings — Edit distance, longest common subsequence, and palindrome partitioning are classic DP problems on strings
• Greedy Number Theory and Bit Manipulation — When greedy optimization fails, DP is used; binary state-compression DP
• Series and Progressions — Fibonacci sequence is a core entry-level DP problem
• Patterns and Series — Recurrence relations in patterns can be modeled and solved using DP