Classic DP Problems

These are the most important DP problems. Master these and you'll be prepared for most interview scenarios.

1. Climbing Stairs

def climbStairs(n):
    """Ways to climb n stairs taking 1 or 2 steps"""
    if n <= 2:
        return n

    prev2, prev1 = 1, 2
    for i in range(3, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current

    return prev1

Pattern: Linear 1D Key: Fibonacci-like recurrence

2. House Robber

def rob(nums):
    """Max money robbing houses, can't rob adjacent"""
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    prev2, prev1 = nums[0], max(nums[0], nums[1])

    for i in range(2, len(nums)):
        current = max(prev1, prev2 + nums[i])
        prev2, prev1 = prev1, current

    return prev1

Pattern: Linear 1D with choice Key: Take or skip current house

3. Coin Change

def coinChange(coins, amount):
    """Minimum coins to make 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

Pattern: Unbounded knapsack Key: Each coin can be used multiple times

4. Longest Increasing Subsequence

def lengthOfLIS(nums):
    """Length of longest increasing subsequence"""
    if not nums:
        return 0

    dp = [1] * len(nums)

    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Pattern: Subsequence Key: O(n²) solution, can optimize to O(n log n)

5. Unique Paths

def uniquePaths(m, n):
    """Paths from top-left to bottom-right"""
    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]

Pattern: Grid paths Key: Can only move right or down

6. Edit Distance

def minDistance(word1, word2):
    """Minimum edits to transform word1 to word2"""
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Base cases
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    # Fill table
    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]

Pattern: 2D string matching Key: Three operations: insert, delete, replace

7. 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]

Pattern: Subsequence matching Key: Match or take max from previous

8. Maximum Subarray (Kadane's Algorithm)

def maxSubArray(nums):
    """Maximum sum of contiguous subarray"""
    max_sum = current_sum = nums[0]

    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)

    return max_sum

Pattern: Linear DP (optimized) Key: Kadane's algorithm - extend or restart

9. Word Break

def wordBreak(s, wordDict):
    """Can s be segmented into words from wordDict?"""
    word_set = set(wordDict)
    dp = [False] * (len(s) + 1)
    dp[0] = True

    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break

    return dp[len(s)]

Pattern: String partition Key: Check all possible splits

10. Partition Equal Subset Sum

def canPartition(nums):
    """Can array be partitioned into two equal sum subsets?"""
    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):
            dp[j] = dp[j] or dp[j - num]

    return dp[target]

Pattern: 0/1 knapsack variant Key: Subset sum to target

Key Takeaway

These 10 problems cover the fundamental DP patterns. Practice them until you can solve them without looking up solutions. Understanding these deeply will prepare you for variations and more complex DP problems in interviews.