StealthCoder

Best Python Solutions for Dynamic Programming LeetCode Problems

2025-08-06

Dynamic Programming (DP) is one of the most feared topics on LeetCode, yet it is also one of the most rewarding once you get the hang of it. Interviewers love DP problems because they test your ability to break a problem into smaller subproblems and reuse solutions efficiently.

In this guide, we’ll cover some of the most common DP problems on LeetCode, walk through the reasoning, and show clean Python solutions you can practice with.

Why dynamic programming matters in interviews

When an interviewer asks you to solve a DP problem, they’re usually checking:

  1. Can you recognize overlapping subproblems?
  2. Do you know how to set up a recurrence relation?
  3. Can you optimize space or time using memoization or tabulation?
  4. Can you explain your thought process clearly?

If you can answer yes to these, you’re well on your way to impressing the interviewer.

Problem 1: Climbing Stairs

Prompt: You are climbing a staircase with n steps. Each time you can climb either 1 or 2 steps. In how many distinct ways can you climb to the top?

This is basically Fibonacci.

def climbStairs(n: int) -> int:
    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]

Complexity: O(n) time and space. You can even reduce it to O(1) space by only keeping the last two values.

Problem 2: House Robber

Prompt: You are a professional robber planning to rob houses along a street. Each house has some money, but you cannot rob two adjacent houses.

def rob(nums) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    dp = [0] * len(nums)
    dp[0], dp[1] = nums[0], 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]

Here the recurrence is simple: at each house, you either rob it (add to dp[i-2]) or skip it (dp[i-1]).

Problem 3: Coin Change

Prompt: Given coins of different denominations and a total amount, return the fewest number of coins to make up that amount. If it’s not possible, return -1.

def coinChange(coins, amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

This is a classic unbounded knapsack problem. The DP state dp[i] means the minimum coins needed for amount i.

Problem 4: Longest Increasing Subsequence (LIS)

Prompt: Given an integer array, find the length of the longest increasing subsequence.

def lengthOfLIS(nums) -> int:
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

This is O(n^2) time. With patience, you can optimize it to O(n log n) using binary search, but for interviews, the DP version is often good enough to show understanding.

Problem 5: Edit Distance

Prompt: Given two words, return the minimum number of operations required to convert one word into the other. Operations: insert, delete, replace.

def minDistance(word1: str, word2: str) -> int:
    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]

This one is a favorite among interviewers because it demonstrates your ability to reason about a two-dimensional DP table.

How to prepare for DP interviews

  1. Start with easy problems like Climbing Stairs.
  2. Move to 1D array DP like House Robber and Coin Change.
  3. Progress into 2D DP like Edit Distance and DP on strings.
  4. Always explain the recurrence before writing code.

Wrap up

Dynamic programming can feel overwhelming at first, but with practice you’ll start recognizing patterns. The best way to prepare is to solve a mix of easy and medium LeetCode problems while making sure you can explain your reasoning out loud.

If you ever get stuck and wish you could instantly see a clear solution with explanation while practicing, tools like StealthCoder can give you that push. It lets you capture a problem mid-practice and see the reasoning step by step, so you can focus on learning instead of being stuck.