DP Practice Problems | Coding Interview DP Problem-Solving Strategies

Introduction

DP problems require practice in defining states and finding recurrence relations. The problems below are solved using both Bottom-Up (fill table from front) and Top-Down (recursion + memo) to master transition relationships.

---

1. Problem 1: Make One

Problem Description

Make integer N into 1. You can use three operations:

1. Divide by 3 if divisible by 3
2. Divide by 2 if divisible by 2
3. Subtract 1

Find minimum number of operations.

Bottom-Up Solution

If dp[i] is “minimum operations to make integer i into 1”, there are three ways to reach i: subtract 1 from i-1, or divide from i/2 or i/3 when divisible. Filling from small numbers allows updating each dp[i] in O(1).

def make_one(n):
    """
    dp[i] = minimum operations to make i into 1
    """
    dp = [0] * (n + 1)
    
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + 1
        
        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i // 2] + 1)
        
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i // 3] + 1)
    
    return dp[n]

print(make_one(10))  # 3 (10 → 9 → 3 → 1)

Step-by-Step Trace:

n=10

dp[0]=0, dp[1]=0

dp[2] = dp[1]+1 = 1
      = min(1, dp[1]+1) = 1 (divide by 2)

dp[3] = dp[2]+1 = 2
      = min(2, dp[1]+1) = 1 (divide by 3)

dp[4] = dp[3]+1 = 2
      = min(2, dp[2]+1) = 2 (divide by 2)

...

dp[9] = dp[8]+1 = 4
      = min(4, dp[3]+1) = 2 (divide by 3)

dp[10] = dp[9]+1 = 3
       = min(3, dp[5]+1) = 3 (divide by 2)

Result: 3

Top-Down Solution

def make_one_recursive(n, memo=None):
    if memo is None:
        memo = {}
    
    if n == 1:
        return 0
    
    if n in memo:
        return memo[n]
    
    result = make_one_recursive(n - 1, memo) + 1
    
    if n % 2 == 0:
        result = min(result, make_one_recursive(n // 2, memo) + 1)
    
    if n % 3 == 0:
        result = min(result, make_one_recursive(n // 3, memo) + 1)
    
    memo[n] = result
    return result

print(make_one_recursive(10))  # 3

---

2. Problem 2: Edit Distance

Problem Description

Find minimum operations to convert string s1 to s2.

• Operations: insert, delete, replace

Solution

def edit_distance(s1, s2):
    """
    dp[i][j] = minimum operations to convert s1[:i] to s2[:j]
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Initial values
    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 s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(
                    dp[i-1][j] + 1,    # delete
                    dp[i][j-1] + 1,    # insert
                    dp[i-1][j-1] + 1   # replace
                )
    
    return dp[m][n]

print(edit_distance("horse", "ros"))  # 3
print(edit_distance("intention", "execution"))  # 5

DP Table Trace:

s1="horse", s2="ros"

    ""  r  o  s
""   0  1  2  3
h    1  1  2  3
o    2  2  1  2
r    3  2  2  2
s    4  3  3  2
e    5  4  4  3

Operations:
1. replace h→r
2. delete o
3. delete e
Result: 3

---

3. Problem 3: Coin Change

Problem Description

Find minimum number of coins to make amount with given coins.

Solution

def coin_change(coins, amount):
    """
    dp[i] = minimum coins to make amount i
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

coins = [1, 2, 5]
print(coin_change(coins, 11))  # 3 (5+5+1)
print(coin_change(coins, 3))   # 2 (2+1)

DP Table Trace:

coins=[1,2,5], amount=11

dp[0]=0
dp[1]=1 (1)
dp[2]=1 (2)
dp[3]=2 (2+1)
dp[4]=2 (2+2)
dp[5]=1 (5)
dp[6]=2 (5+1)
dp[7]=2 (5+2)
dp[8]=3 (5+2+1)
dp[9]=3 (5+2+2)
dp[10]=2 (5+5)
dp[11]=3 (5+5+1)

Result: 3

Path Tracking

def coin_change_with_path(coins, amount):
    dp = [float('inf')] * (amount + 1)
    parent = [-1] * (amount + 1)
    dp[0] = 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
                parent[i] = coin
    
    if dp[amount] == float('inf'):
        return -1, []
    
    path = []
    current = amount
    while current > 0:
        path.append(parent[current])
        current -= parent[current]
    
    return dp[amount], path

count, path = coin_change_with_path([1, 2, 5], 11)
print(f"Min count: {count}, Coins: {path}")  # 3, [5, 5, 1]

---

4. Problem 4: Longest Increasing Subsequence (LIS)

Problem Description

Find maximum length of increasing subsequence in array.

O(n²) Solution

def lis(arr):
    """
    dp[i] = LIS length ending at index i
    """
    n = len(arr)
    dp = [1] * n
    
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 4 ([2, 3, 7, 101])

O(n log n) Solution

from bisect import bisect_left

def lis_optimized(arr):
    """
    Optimized with binary search
    """
    tails = []
    
    for num in arr:
        pos = bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    
    return len(tails)

print(lis_optimized([10, 9, 2, 5, 3, 7, 101, 18]))  # 4

How O(n log n) Works:

arr = [10, 9, 2, 5, 3, 7, 101, 18]

tails maintains smallest tail for each length

num=10: tails=[10]
num=9:  tails=[9]     (replace 10)
num=2:  tails=[2]     (replace 9)
num=5:  tails=[2,5]   (append)
num=3:  tails=[2,3]   (replace 5)
num=7:  tails=[2,3,7] (append)
num=101:tails=[2,3,7,101] (append)
num=18: tails=[2,3,7,18]  (replace 101)

Length: 4

---

5. Problem 5: Knapsack

Problem Description

Maximize value in knapsack with weight limit W.

Solution

def knapsack(weights, values, W):
    """
    dp[i][w] = max value considering first i items with weight w
    """
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(
                    dp[i-1][w],
                    dp[i-1][w - weights[i-1]] + values[i-1]
                )
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][W]

weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
W = 7
print(knapsack(weights, values, W))  # 9 (weights 3+4, values 4+5)

DP Table Trace:

weights=[1,3,4,5], values=[1,4,5,7], W=7

     w: 0  1  2  3  4  5  6  7
i=0:    0  0  0  0  0  0  0  0
i=1(1): 0  1  1  1  1  1  1  1
i=2(3): 0  1  1  4  5  5  5  5
i=3(4): 0  1  1  4  5  6  6  9
i=4(5): 0  1  1  4  5  7  7  9

Result: dp[4][7]=9
Items: weight 3 (value 4) + weight 4 (value 5)

Space Optimization

def knapsack_optimized(weights, values, W):
    """
    Space optimization with 1D array
    """
    dp = [0] * (W + 1)
    
    for i in range(len(weights)):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[W]

print(knapsack_optimized(weights, values, W))  # 9

---

6. Problem 6: Longest Common Subsequence (LCS)

Problem Description

Find longest common subsequence of two strings.

Solution

def lcs(s1, s2):
    """
    dp[i][j] = LCS length of s1[:i] and s2[:j]
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[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]

print(lcs("ABCDGH", "AEDFHR"))  # 3 ("ADH")

LCS with Path Reconstruction

def lcs_with_string(s1, s2):
    """
    Return LCS string, not just length
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Build DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    # Backtrack to find string
    result = []
    i, j = m, n
    
    while i > 0 and j > 0:
        if s1[i-1] == s2[j-1]:
            result.append(s1[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    
    return ''.join(reversed(result))

print(lcs_with_string("ABCDGH", "AEDFHR"))  # "ADH"

---

7. Problem 7: House Robber

Problem Description

Rob houses for maximum money, but cannot rob adjacent houses.

Solution

def rob(houses):
    """
    dp[i] = max money robbing up to house i
    """
    if not houses:
        return 0
    if len(houses) == 1:
        return houses[0]
    
    dp = [0] * len(houses)
    dp[0] = houses[0]
    dp[1] = max(houses[0], houses[1])
    
    for i in range(2, len(houses)):
        dp[i] = max(dp[i-1], dp[i-2] + houses[i])
    
    return dp[-1]

# Test
print(rob([2, 7, 9, 3, 1]))  # 12 (2+9+1)

Space Optimized:

def rob_optimized(houses):
    """
    O(1) space
    """
    if not houses:
        return 0
    if len(houses) == 1:
        return houses[0]
    
    prev2 = houses[0]
    prev1 = max(houses[0], houses[1])
    
    for i in range(2, len(houses)):
        current = max(prev1, prev2 + houses[i])
        prev2, prev1 = prev1, current
    
    return prev1

---

Practical Tips

DP Problem Approach (5 Steps)

# 1. Define subproblems
# dp[i] = "optimal solution up to i"

# 2. Find recurrence relation
# dp[i] = f(dp[i-1], dp[i-2], ...)

# 3. Set initial values
# dp[0] = ..., dp[1] = ...

# 4. Choose implementation
# Top-Down (recursion) vs Bottom-Up (iteration)

# 5. Optimize
# Space optimization, skip unnecessary calculations

Debugging Tips

def debug_dp(dp):
    """Print DP table"""
    for i, row in enumerate(dp):
        print(f"dp[{i}]: {row}")

# Usage
dp = [[0] * 5 for _ in range(3)]
debug_dp(dp)

# Print 1D DP
def debug_dp_1d(dp):
    print("dp:", dp)

# Verify recurrence
def verify_recurrence(dp, i):
    """Check if dp[i] follows recurrence relation"""
    expected = calculate_expected(dp, i)
    actual = dp[i]
    assert expected == actual, f"dp[{i}]: expected {expected}, got {actual}"

Common Mistakes

# ❌ Wrong: Forgot initial values
dp = [0] * n
for i in range(n):
    dp[i] = dp[i-1] + dp[i-2]  # dp[0], dp[1] not set!

# ✅ Correct: Set initial values
dp = [0] * n
dp[0] = 1
dp[1] = 1
for i in range(2, n):
    dp[i] = dp[i-1] + dp[i-2]

# ❌ Wrong: Index out of bounds
for i in range(n):
    dp[i] = dp[i-1] + dp[i-2]  # i=0, i=1 error!

# ✅ Correct: Start from valid index
for i in range(2, n):
    dp[i] = dp[i-1] + dp[i-2]

---

Summary

Key Points

1. Approach: Subproblems → Recurrence → Initial values → Implementation
2. Patterns: 1D DP, 2D DP, Knapsack, LCS, LIS
3. Optimization: Space (1D array), Time (binary search)
4. Practice: Solve many problems

Problem Type Checklist

Type	Recurrence	Example
1D DP	dp[i] = f(dp[i-1])	Make One, Climbing Stairs
2D DP	dp[i][j] = f(dp[i-1][j], dp[i][j-1])	Edit Distance, LCS
Knapsack	dp[i][w] = max(take, don't take)	0-1 Knapsack
LIS	dp[i] = max(dp[j]+1) for j<i	LIS

Next Steps

• Dynamic Programming Basics
• DP Patterns
• Sorting Problems

---

Recommended Problems

Baekjoon

• 1463: Make One
• 2293: Coin 1
• 9251: LCS
• 12865: Ordinary Knapsack

LeetCode

• LeetCode 70: Climbing Stairs
• LeetCode 198: House Robber
• LeetCode 322: Coin Change
• LeetCode 300: Longest Increasing Subsequence
• LeetCode 72: Edit Distance
• LeetCode 1143: Longest Common Subsequence
• LeetCode 416: Partition Equal Subset Sum

Programmers

• Express with N
• Integer Triangle

---

Related Posts

• Greedy Algorithm | “Best Choice Every Step” Complete Guide
• Backtracking | Exhaustive Search Algorithm Complete Guide
• Algorithm Series Full Index
• Arrays and Lists | Essential Data Structure Complete Guide
• Stack and Queue | Essential Data Structure Complete Guide
• Hash Table | O(1) Search Data Structure Complete Guide

---

Keywords

Dynamic Programming, DP, Problem Solving, Make One, Edit Distance, Coin Change, LIS, Knapsack, LCS, Coding Interview, Algorithm, Optimization