Dynamic Programming Examples: 35 Problems to Improve Problem-Solving Skills

Dynamic programming (DP) is a powerful problem solving technique that helps break complex problems into smaller subproblems. Solving each only once and storing the results to avoid redundant computations.

Whether you are preparing for coding interviews or just want to improving algorithmic thinking practicing Dynamic Programming Examples is one of the best ways to master this approach.

In this blog, We have listed top 15 easy, 10 medium and 10 hard DP problems providing a structured path to build-up skills step by step.

Keep reading…

Top 15 Easy Level Dynamic Programming Example Problems

Here are the top 15 easy-level Dynamic Programming example problems to help you build a strong foundation and improve your problem solving skills.

1. Fibonacci Numbers

➢ Problem Statement:

Given an integer n, find the nth Fibonacci number. The Fibonacci sequence is defined as:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2), for n ≥ 2

➢ Solution (Using DP — Bottom-Up Approach)

def fibonacci(n):
    if n <= 1:
        return n
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(fibonacci(10))  # Output: 55

2. Climbing Stairs

➢ Problem Statement:

You are climbing a staircase. It takes n steps to reach the top. You can either climb 1 or 2 steps at a time. How many distinct ways can you reach the top?

➢ Solution:

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

print(climbStairs(5))  # Output: 8

3. House Robber

➢ Problem Statement:

Given an array nums representing money in each house, find the maximum amount of money you can rob without robbing two adjacent houses.

➢ Solution:

def rob(nums):
    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], nums[i] + dp[i-2])
    return dp[-1]

print(rob([2,7,9,3,1]))  # Output: 12

4. Minimum Cost Climbing Stairs

➢ Problem Statement:

Each step has a cost cost[i]. You can start from index 0 or 1. Find the minimum cost to reach the top

➢ Solution:

def minCostClimbingStairs(cost):
    n = len(cost)
    dp = [0] * (n+1)
    for i in range(2, n+1):
        dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
    return dp[n]

print(minCostClimbingStairs([10, 15, 20]))  # Output: 15

5. Coin Change (Minimum Coins)

➢ Problem Statement:

Given coins [1,2,5] and amount 11, find the minimum number of coins needed to make that amount.

➢ Solution:

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

print(coinChange([1,2,5], 11))  # Output: 3 (5+5+1)

Also Read: Automation Testing Languages

6. Longest Increasing Subsequence

➢ Problem Statement:

Given an array nums, find the length of the longest increasing subsequence.

➢ Solution:

def lengthOfLIS(nums):
    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)

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

7. Maximum Subarray Sum (Kadane’s Algorithm)

➢ Problem Statement:

Find the maximum sum of a contiguous subarray in a given array.

➢ Solution:

def maxSubArray(nums):
    max_sum = nums[0]
    current_sum = nums[0]
    for i in range(1, len(nums)):
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)
    return max_sum

print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))  # Output: 6

8. Edit Distance (Levenshtein Distance)

➢ Problem Statement:

Find the minimum operations (insert, delete, replace) required to convert word1 to word2.

➢ Solution:

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):
        for j in range(n+1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif 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]

print(minDistance("horse", "ros"))  # Output: 3

9. Unique Paths in a Grid

➢ Problem Statement:

Find the number of ways to reach the bottom-right of an m x n grid starting from the top-left.

➢ Solution:

def uniquePaths(m, n):
    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[-1][-1]

print(uniquePaths(3, 7))  # Output: 28

10. Partition Equal Subset Sum

➢ Problem Statement:

Determine if the array can be partitioned into two subsets with equal sum.

➢ Solution:

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = set([0])
    for num in nums:
        dp |= {num + x for x in dp}
        if target in dp:
            return True
    return False

print(canPartition([1,5,11,5]))  # Output: True

11. Tribonacci Number

➢ Problem Statement:

The Tribonacci sequence is defined as:

• T(0) = 0, T(1) = 1, T(2) = 1
• T(n) = T(n-1) + T(n-2) + T(n-3), for n ≥ 3

Given an integer n, return T(n).

➢ Solution:

def tribonacci(n):
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 1
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
    return dp[n]

print(tribonacci(4))  # Output: 4
print(tribonacci(10))  # Output: 149

12. Decode Ways

➢ Problem Statement:

A message containing letters A-Z is encoded using the following mapping:

• 'A' -> 1, 'B' -> 2, ..., 'Z' -> 26
• Given a string s consisting of digits, count the number of ways it can be decoded.

➢ Solution:

def numDecodings(s):
    if not s or s[0] == '0':
        return 0
    n = len(s)
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1
    
    for i in range(2, n + 1):
        one_digit = int(s[i - 1])
        two_digits = int(s[i - 2:i])
        
        if one_digit >= 1:
            dp[i] += dp[i - 1]
        if 10 <= two_digits <= 26:
            dp[i] += dp[i - 2]
    
    return dp[n]

print(numDecodings("226"))  # Output: 3
print(numDecodings("12"))   # Output: 2

13. Best Time to Buy and Sell Stock

➢ Problem Statement:

Given an array prices[] where prices[i] is the stock price on day i, find the maximum profit you can achieve by buying and selling once.

➢ Solution:

def maxProfit(prices):
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)
    return max_profit

print(maxProfit([7,1,5,3,6,4]))  # Output: 5
print(maxProfit([7,6,4,3,1]))    # Output: 0

14. Counting Bits

➢ Problem Statement:

Given an integer n, return an array ans where ans[i] is the number of 1’s in the binary representation of i for 0 ≤ i ≤ n.

➢ Solution:

def countBits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

print(countBits(5))  # Output: [0,1,1,2,1,2]

15. Target Sum

➢ Problem Statement:

You are given an array nums[] and a target sum S. Find the number of ways to assign + or - signs to elements to achieve S.

➢ Solution:

def findTargetSumWays(nums, target):
    total = sum(nums)
    if (total + target) % 2 == 1 or total < abs(target):
        return 0
    s = (total + target) // 2
    dp = [0] * (s + 1)
    dp[0] = 1

    for num in nums:
         for j in range(s, num - 1, -1):
              dp[j] += dp[j - num]
    return dp[s]

print(findTargetSumWays([1,1,1,1,1], 3))  # Output: 5

Also Read: Difference Between Primitive and Reference Data Types in Java

Top 10 Medium Level Dynamic Programming Example Problems

Here are the top 10 medium-level Dynamic Programming examples to strengthen your problem solving skills and deepen your DP understanding.

1. Longest Palindromic Subsequence

➢ Problem Statement:

Given a string s, find the length of the longest palindromic subsequence in s. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order.

➢ Example:

Input: "bbbab"
Output: 4
Explanation: The longest palindromic subsequence is "bbbb" with length 4.

➢ Solution:

This problem can be solved using dynamic programming with the following observations:

1. If s[i] == s[j], then these characters can be part of the LPS (Longest Palindromic Subsequence), so the length increases by 2 and we move inward:

dp[i][j] = 2 + dp[i + 1][j - 1]

2. If s[i] != s[j], we have two choices:

• Ignore s[i] and solve for s[i+1...j]
• Ignore s[j] and solve for s[i...j-1]
• Take the maximum of both:

dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

➢ Code Implementation (Bottom-up DP):

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    # Base case: single character palindromes
    for i in range(n):
        dp[i][i] = 1  

    for length in range(2, n+1):  
            for i in range(n-length+1):
                j = i + length - 1
                if s[i] == s[j]:
                    dp[i][j] = 2 + dp[i+1][j-1]
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])

    return dp[0][n-1]

➢ Time Complexity: O(n²)
➢ Space Complexity: O(n²)

2. Coin Change Problem

➢ Problem Statement:

Given an array of coins coins[] of size n representing different denominations and an integer amount, find the minimum number of coins required to make up the amount. If it's not possible, return -1.

➢ Example:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: We can make 11 using 5 + 5 + 1.

➢ Solution:

We define dp[i] as the minimum number of coins needed to get the sum i.

• Base Case: dp[0] = 0 (0 coins are needed for amount 0)
• Transition Formula: dp[i]=min⁡(dp[i−coin]+1)∀ coin in coinsdp[i] = \min(dp[i — coin] + 1) \quad \forall \text{ coin in coins}dp[i]=min(dp[i−coin]+1)∀ coin in coins
• We iterate over all possible sums from 1 to amount and check for each coin denomination.

➢ Code Implementation (Bottom-up DP):

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  

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

➢ Time Complexity: O(n × amount)
➢ Space Complexity: O(amount)

3. Subset Sum Problem

➢ Problem Statement:

Given an array arr[] of n positive integers and a target sum sum, determine if there exists a subset with sum equal to sum.

➢ Example:

Input: arr = [2, 3, 7, 8, 10], sum = 11
Output: True
Explanation: Subset {3, 8} gives sum 11.

➢ Solution:

Define dp[i][j] as True if a subset of the first i elements has a sum equal to j, else False.

1. Base Case:

• dp[0][0] = True (empty subset sums to 0)
• If sum > 0 and no elements are considered, dp[0][sum] = False

2. Transition Formula:

• If arr[i-1] is greater than j, we exclude it:
• dp[i][j] = dp[i — 1][j]
• Otherwise, we check two cases:
• dp[i][j] = dp[i - 1][j] OR dp[i - 1][j - arr[i-1]]

➢ Code Implementation:

def subsetSum(arr, target):
    n = len(arr)
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    
    for i in range(n + 1):
        dp[i][0] = True  

    for i in range(1, n + 1):
            for j in range(1, target + 1):
                if arr[i-1] > j:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j] or dp[i-1][j - arr[i-1]]
    return dp[n][target]

➢ Time Complexity: O(n×sum)
➢ Space Complexity: O(n×sum)

4. Edit Distance

➢ Problem Statement:

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. Allowed operations:

• Insert a character
• Delete a character
• Replace a character

➢ Example:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:

• Replace ‘h’ → ‘r’
• Remove ‘o’
• Remove ‘e’

➢ Solution:

Define dp[i][j] as the minimum operations to convert word1[0:i] to word2[0:j].

1. Base Case: If one string is empty, operations equal the length of the other string.

2. Transition Formula:

• If word1[i-1] == word2[j-1], no change needed: dp[i][j] = dp[i-1][j-1]
• Else, choose the minimum of:
• Insert: dp[i][j-1] + 1
• Delete: dp[i-1][j] + 1
• Replace: dp[i-1][j-1] + 1

3. Code Implementation:

def editDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m+1):
        for j in range(n+1):
            if i == 0:
                dp[i][j] = j  
            elif j == 0:
                dp[i][j] = i  
            elif 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]

➢ Time Complexity: O(m × n)
➢ Space Complexity: O(m × n)

5. Unique Paths

➢ Problem Statement:

You are given an m x n grid. A robot starts at the top-left corner (0,0) and wants to reach the bottom-right corner (m-1, n-1). The robot can only move right or down at any point. Find the number of unique paths.

➢ Example:

• Input: m = 3, n = 7
• Output: 28
• Explanation: There are 28 ways to reach (2,6) from (0,0).

➢ Solution:

Define dp[i][j] as the number of ways to reach cell (i, j).

1. Base Case:

• dp[0][j] = 1 (Only one way to move right)
• dp[i][0] = 1 (Only one way to move down)

2. Transition Formula:

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

➢ Code Implementation:

def uniquePaths(m, n):
    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]

➢ Time Complexity: O(m × n)
➢ Space Complexity: O(m × n), can be optimized to O(n).

Also Read: PHP Project Topics

6. Partition Equal Subset Sum

➢ Problem Statement:

Given an array of positive integers, determine if the array can be partitioned into two subsets with equal sums.

➢ Example:

• Input: nums = [1, 5, 11, 5]
• Output: True
• Explanation: Two subsets {1, 5, 5} and {11} both have sum 11.

➢ Solution:

• The total sum must be even for partitioning to be possible.
• Convert this problem to Subset Sum Problem:
• Check if a subset exists with sum total_sum / 2.
• Use DP to solve it.

➢ Code Implementation:

def canPartition(nums):
    total_sum = sum(nums)
    if total_sum % 2 != 0:
        return False
    
    target = total_sum // 2
    n = len(nums)
    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

➢ Time Complexity: O(n × sum)
➢ Space Complexity: O(sum)

7. Maximum Product Subarray

➢ Problem Statement:

Given an array nums[], find the contiguous subarray that has the maximum product.

➢ Example:

• Input: nums = [2, 3, -2, 4]
• Output: 6
• Explanation: The subarray [2, 3] has the maximum product 6.

➢ Solution:

• Maintain max_product and min_product at each step.
• If nums[i] is negative, swap max_product and min_product.
• Update max_product and min_product accordingly.

➢ Code Implementation:

def maxProduct(nums):
    if not nums:
        return 0
    
    max_prod = min_prod = result = nums[0]
    
    for i in range(1, len(nums)):
        if nums[i] < 0:
            max_prod, min_prod = min_prod, max_prod
        max_prod = max(nums[i], nums[i] * max_prod)
        min_prod = min(nums[i], nums[i] * min_prod)
        result = max(result, max_prod)
    
    return result

➢ Time Complexity: O(n)
➢ Space Complexity: O(1)

8. Number of Ways to Decode a String

➢ Problem Statement:

A string containing digits (1–9) can be decoded into letters (A-Z: 1-26). Given an encoded string, count the number of ways to decode it.

➢ Example:

• Input: "226"
• Output: 3
• Explanation: "226" can be decoded as "BZ", "VF", or "BBF".

➢ Solution:

• Define dp[i] as the number of ways to decode s[0:i].
• If s[i] != '0', take dp[i] = dp[i-1].
• If s[i-1]s[i] is a valid two-digit decode (10-26), include dp[i-2].

➢ Code Implementation:

def numDecodings(s):
    if not s or s[0] == '0':
        return 0
    
    n = len(s)
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1  

    for i in range(1, n):
        if s[i] != '0':
            dp[i+1] = dp[i]
        if 10 <= int(s[i-1:i+1]) <= 26:
            dp[i+1] += dp[i-1]

    return dp[n]  

➢ Time Complexity: O(n)
➢ Space Complexity: O(n), can be optimized to O(1).

9. Best Time to Buy and Sell Stock with Cooldown

➢ Problem Statement:

You are given an array prices[] where prices[i] is the price of a stock on the i-th day. You may buy one share of stock on any day and sell it later, but after selling, you must wait one day (cooldown) before buying again. Find the maximum profit you can achieve.

➢ Example:

• Input: prices = [1, 2, 3, 0, 2]
• Output: 3

➢ Explanation:

• Buy on day 0 (price = 1), sell on day 2 (price = 3) → Profit = 2
• Cooldown on day 3
• Buy on day 3 (price = 0), sell on day 4 (price = 2) → Profit = 2
• Total profit = 2 + 1 = 3

➢ Solution:

We define three states:

1. hold[i] → Maximum profit if holding a stock on day i.
2. sell[i] → Maximum profit if selling a stock on day i.
3. cooldown[i] → Maximum profit if in cooldown on day i.

➢ Recurrence Relations:

• If holding stock today:

hold[i] = max(hold[i - 1], cooldown[i - 1] - prices[i])

• If selling stock today:

sell[i]=hold[i − 1] + prices[i]

• If in cooldown today:

cooldown[i] = max⁡(cooldown[i − 1], sell[i − 1])

➢ Final Answer:

max⁡(sell[n − 1], cooldown[n − 1])

➢ Code Implementation:

def maxProfit(prices):
    if not prices:
        return 0
    
    n = len(prices)
    hold, sell, cooldown = [0] * n, [0] * n, [0] * n
    
    hold[0] = -prices[0]
    
    for i in range(1, n):
        hold[i] = max(hold[i-1], cooldown[i-1] - prices[i])
        sell[i] = hold[i-1] + prices[i]
        cooldown[i] = max(cooldown[i-1], sell[i-1])
    
    return max(sell[-1], cooldown[-1])

➢ Time Complexity: O(n)
➢ Space Complexity: O(n), can be optimized to O(1).

10. Interleaving String

➢ Problem Statement:

Given three strings s1, s2, and s3, return True if s3 is formed by an interleaving of s1 and s2. An interleaving means maintaining the relative order of characters but merging the two strings.

➢ Example:

• Input: s1 = "abc", s2 = "def", s3 = "adbcef"
• Output: True
• Explanation: "adbcef" can be formed by interleaving "abc" and "def".

➢ Solution:

Define dp[i][j] as True if s3[0:i+j] can be formed using s1[0:i] and s2[0:j].

➢ Recurrence Relations:

• If the current character of s3 matches s1[i-1], we check dp[i-1][j].
• If the current character of s3 matches s2[j-1], we check dp[i][j-1].

dp[i][j] = (dp[i − 1][j] if s1[i − 1] = s3[i + j − 1]) OR (dp[i][j − 1] if s2[j − 1] = s3[i + j − 1])

➢ Base Case:

• dp[0][0] = True (empty strings match).
• dp[i][0] = True if s1[:i] == s3[:i].
• dp[0][j] = True if s2[:j] == s3[:j].

➢ Code Implementation:

def isInterleave(s1, s2, s3):
    if len(s1) + len(s2) != len(s3):
        return False
    
    m, n = len(s1), len(s2)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    
    dp[0][0] = True
    
    for i in range(1, m + 1):
        dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]

    for j in range(1, n + 1):
        dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or \
                       (dp[i][j-1] and s2[j-1] == s3[i+j-1])

    return dp[m][n]

➢ Time Complexity: O(m × n)
➢ Space Complexity: O(m × n), can be optimized to O(n).

Also Read: Issues of Code Generation

Top 10 Hard Level Dynamic Programming Example Problems

Here are the top 10 hard-level Dynamic Programming examples to challenge your skills and master advanced DP techniques.

1. Longest Increasing Subsequence (LIS)

➢ Problem Statement:

Given an array of integers, find the length of the longest increasing subsequence (LIS). A subsequence is a sequence derived by deleting some elements without changing the order of the remaining elements.

➢ Example:

• Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
• Output: 4
• Explanation: The longest increasing subsequence is [2, 3, 7, 101].

➢ Solution Approach (Dynamic Programming)

1. Define dp[i] as the length of the longest increasing subsequence that ends at index i.

2. Initialize dp array with 1, because each element alone is an increasing subsequence.

3. Iterate over the array with two loops:

• Outer loop i from 1 to n-1.
• Inner loop j from 0 to i-1, checking if nums[j] < nums[i], then update dp[i] = max(dp[i], dp[j] + 1).

4. The result is the maximum value in the dp array.

➢ Code Implementation:

def lengthOfLIS(nums):
    n = len(nums)
    if n == 0:
        return 0
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# Example usage
print(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]))  # Output: 4

➢ Time Complexity: O(n^2), but can be optimized to O(n log n) using binary search.

2. Edit Distance (Levenshtein Distance)

➢ Problem Statement:

Given two strings word1 and word2, return the minimum number of operations required to convert word1 into word2. Allowed operations:

• Insert a character
• Delete a character
• Replace a character

➢ Example:

• Input: word1 = "horse", word2 = "ros"
• Output: 3

➢ Explanation:

• horse → rorse (replace 'h' with 'r')
• rorse → rose (delete 'r')
• rose → ros (delete 'e')

➢ Solution Approach (Dynamic Programming)

1. Define dp[i][j] as the minimum edit distance for word1[0:i] and word2[0:j].

2. Base cases:

• dp[i][0] = i (deleting all characters in word1).
• dp[0][j] = j (inserting all characters in word2).

3. Recurrence relation:

• If word1[i-1] == word2[j-1], then dp[i][j] = dp[i-1][j-1] (no change needed).
• Otherwise, dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1) (delete, insert, replace).

➢ Code Implementation:

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):
        for j in range(n + 1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif 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]

# Example usage
print(minDistance("horse", "ros"))  # Output: 3

➢ Time Complexity: O(m * n)

3. Maximum Profit in Job Scheduling

➢ Problem Statement:

Given n jobs, each represented as (startTime[i], endTime[i], profit[i]), find the maximum profit that can be earned by scheduling jobs such that no two jobs overlap.

➢ Example:

startTime = [1, 2, 3, 3]
endTime = [3, 4, 5, 6]
profit = [50, 10, 40, 70]

Output: 120

➢ Solution Approach (Dynamic Programming + Binary Search)

1. Sort jobs by endTime.
2. Use DP where dp[i] stores the maximum profit by considering jobs up to index i.
3. Use binary search to find the last job that does not overlap.
4. Recurrence relation:
   dp[i] = max(dp[i-1], profit[i] + dp[last_non_conflicting_job])

➢ Code Implementation:

from bisect import bisect_right

def jobScheduling(startTime, endTime, profit):
    jobs = sorted(zip(endTime, startTime, profit))
    dp = [(0, 0)]  # (endTime, maxProfit)

    for e, s, p in jobs:
        i = bisect_right(dp, (s,)) - 1
        maxProfit = max(dp[-1][1], dp[i][1] + p)
        dp.append((e, maxProfit))

    return dp[-1][1]

# Example usage
print(jobScheduling([1,2,3,3], [3,4,5,6], [50,10,40,70]))  # Output: 120

➢ Time Complexity: O(n log n)

4. Burst Balloons

➢ Problem Statement:

Given n balloons, numbered from 0 to n-1, each with a positive integer value, maximize coins by bursting them. The coins collected by bursting i is nums[i-1] * nums[i] * nums[i+1].

➢ Example:

• Input: nums = [3, 1, 5, 8]
• Output: 167

➢ Solution Approach (DP with Interval Subproblems)

1. Define dp[left][right] as the max coins obtained from nums[left:right].
2. Iterate over possible balloon bursts in the interval, updating dp[left][right].

➢ Code Implementation:

def maxCoins(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    
    for length in range(2, n):
        for left in range(n - length):
            right = left + length
            dp[left][right] = max(nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right] for i in range(left + 1, right))
    
    return dp[0][-1]

# Example usage
print(maxCoins([3,1,5,8]))  # Output: 167

➢ Time Complexity: O(n^3)

5. Wildcard Matching

➢ Problem Statement:

Given two strings s and p, where p contains wildcard characters:

• ? matches any single character.
• * matches any sequence of characters (including empty sequence). Determine if p matches s.

➢ Example:

• Input: s = "adceb", p = "*a*b"
• Output: True
• Explanation: The pattern *a*b can match adceb.

➢ Solution Approach (DP):

1. Define dp[i][j] as True if s[0:i] matches p[0:j].

2. Base cases:

• dp[0][0] = True (empty string matches empty pattern).
• If p[j-1] == '*', dp[0][j] = dp[0][j-1] (match zero characters).

3. Transition:

• If p[j-1] == s[i-1] or p[j-1] == '?', dp[i][j] = dp[i-1][j-1].
• If p[j-1] == '*', dp[i][j] = dp[i-1][j] or dp[i][j-1].

➢ Code Implementation:

def isMatch(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    
    for j in range(1, n + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-1]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j-1] == s[i-1] or p[j-1] == '?':
                dp[i][j] = dp[i-1][j-1]
            elif p[j-1] == '*':
                dp[i][j] = dp[i-1][j] or dp[i][j-1]

    return dp[m][n]

# Example usage
print(isMatch("adceb", "*a*b"))  # Output: True

➢ Time Complexity: O(m * n)

Also Read: Generative AI Projects

6. Palindrome Partitioning II

➢ Problem Statement:

Given a string s, partition it such that every substring is a palindrome, and return the minimum cuts needed.

➢ Example:

Input: s = "aab"
Output: 1
Explanation: We can partition "aab" as "aa" | "b", needing 1 cut.

➢ Solution Approach (DP)

1. Precompute palindromes:
   Use isPalindrome[i][j] to check if s[i:j] is a palindrome.
2. Define dp[i] as the minimum cuts needed for s[0:i].
3. Transition:
   If s[j:i] is a palindrome, dp[i] = min(dp[i], dp[j-1] + 1).

➢ Code Implementation:

def minCut(s):
    n = len(s)
    isPalindrome = [[False] * n for _ in range(n)]
    dp = [float('inf')] * n

    for i in range(n):
        for j in range(i + 1):
            if s[j] == s[i] and (i - j <= 1 or isPalindrome[j+1][i-1]):
                isPalindrome[j][i] = True

    for i in range(n):
        if isPalindrome[0][i]:
            dp[i] = 0
        else:
            for j in range(i):
                if isPalindrome[j+1][i]:
                    dp[i] = min(dp[i], dp[j] + 1)
    
    return dp[n-1]

# Example usage
print(minCut("aab"))  # Output: 1

➢ Time Complexity: O(n^2)

7. Largest Rectangle in Histogram

➢ Problem Statement:

Given an array representing the heights of histogram bars, find the largest rectangle that can be formed.

➢ Example:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The largest rectangle is formed using [5,6], which has area 5 × 2 = 10.

➢ Solution Approach (Stack + DP)

1. Use a monotonic stack to track increasing heights.
2. When a height decreases, compute areas with previously stored heights.

➢ Code Implementation:

def largestRectangleArea(heights):
    stack = []
    max_area = 0
    heights.append(0)  # Sentinel value

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

# Example usage
print(largestRectangleArea([2,1,5,6,2,3]))  # Output: 10

➢ Time Complexity: O(n)

8. Optimal Binary Search Tree

➢ Problem Statement:

Given keys [10, 20, 30] with search probabilities [0.1, 0.2, 0.7], construct a BST that minimizes the expected search cost.

➢ Example:

Input:

keys = [10, 20, 30]
freq = [0.1, 0.2, 0.7]

Output: 1.4

➢ Solution Approach (DP)

1. Define dp[i][j] as the minimum cost for keys i to j.
2. Transition formula:

dp[i][j] = min(dp[i][k-1] + dp[k+1][j] + sum of frequencies)

where k is the root.

➢ Code Implementation:

def optimalBST(keys, freq):
    n = len(keys)
    dp = [[0] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = freq[i]

    for L in range(2, n + 1):
        for i in range(n - L + 1):
            j = i + L - 1
            dp[i][j] = float('inf')
            freq_sum = sum(freq[i:j+1])

            for r in range(i, j + 1):
                cost = (dp[i][r-1] if r > i else 0) + (dp[r+1][j] if r < j else 0) + freq_sum
                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n-1]

# Example usage
print(optimalBST([10, 20, 30], [0.1, 0.2, 0.7]))  # Output: 1.4

➢ Time Complexity: O(n^3)

9. Word Break II

➢ Problem Statement:

Given a string s and a dictionary wordDict, return all possible sentences formed using words from wordDict.

➢ Example:

Input:

s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]

Output:

["cats and dog", "cat sand dog"]

➢ Solution Approach (DP + Backtracking)

1. Use dp[i] to store possible words forming s[0:i].
2. Use backtracking to generate sentences.

➢ Code Implementation:

from collections import defaultdict

def wordBreak(s, wordDict):
    wordSet = set(wordDict)
    dp = defaultdict(list)
    dp[0] = [""]

    for i in range(1, len(s) + 1):
        for j in range(i):
            if s[j:i] in wordSet:
                dp[i] += [x + ("" if x == "" else " ") + s[j:i] for x in dp[j]]

    return dp[len(s)]

# Example usage
print(wordBreak("catsanddog", ["cat", "cats", "and", "sand", "dog"]))

➢ Time Complexity: O(n^2)

10. Galactic Relocation Problem

➢ Problem Statement:

A galactic empire needs to relocate its citizens between N planets, each with limited resources. Each planet i has a capacity C[i] (maximum citizens it can hold) and a relocation cost R[i][j] (cost of moving one citizen from planet i to planet j).

➢ You are given:

• P[i]: Initial number of citizens on each planet.
• C[i]: Maximum capacity of each planet.
• R[i][j]: A square matrix representing the cost to move one citizen from planet i to planet j.
• Goal: Minimize the total relocation cost so that no planet exceeds its capacity.

➢ Constraints:

• 1 ≤ N ≤ 50 (Planets count)
• 0 ≤ P[i] ≤ 10^6 (Initial population)
• 1 ≤ C[i] ≤ 10^6 (Capacity)
• 0 ≤ R[i][j] ≤ 10^9 (Relocation cost)

➢ Example:

N = 3  
P = [7, 3, 1]  
C = [5, 5, 5]  
R = [
  [0, 2, 3],  
  [2, 0, 4],  
  [3, 4, 0]  
]

Output: 6

➢ Explanation:

• Move 2 citizens from planet 1 to 2 → Cost 2 × 2 = 4
• Move 1 citizen from planet 1 to 3 → Cost 1 × 3 = 3
• Total cost = 6

➢ Solution Approach (Dynamic Programming + Min Cost Flow)

1. Define dp[i][j] as the minimum cost to distribute excess citizens from planet 0 to i with j citizens already moved.
2. Recursive Transition:

• If i has excess citizens, try moving them to j minimizing cost using R[i][j].
• Use a flow-based DP approach to ensure capacities aren’t exceeded.

➢ Code Implementation:

import heapq

def galactic_relocation(N, P, C, R):
    excess = [P[i] - C[i] for i in range(N)]
    surplus = [(i, excess[i]) for i in range(N) if excess[i] > 0]
    deficit = [(i, -excess[i]) for i in range(N) if excess[i] < 0]
    
    pq = []
    for (src, s_qty) in surplus:
        for (dst, d_qty) in deficit:
            if s_qty == 0 or d_qty == 0:
                continue
            move = min(s_qty, d_qty)
            heapq.heappush(pq, (R[src][dst] * move, src, dst, move))

    total_cost = 0
    while pq:
        cost, src, dst, move = heapq.heappop(pq)
        total_cost += cost
        for i in range(len(surplus)):
            if surplus[i][0] == src:
                surplus[i] = (src, surplus[i][1] - move)
        for j in range(len(deficit)):
            if deficit[j][0] == dst:
                deficit[j] = (dst, deficit[j][1] - move)
    
    return total_cost

# Example usage
N = 3
P = [7, 3, 1]
C = [5, 5, 5]
R = [
  [0, 2, 3],
  [2, 0, 4],
  [3, 4, 0]
]

print(galactic_relocation(N, P, C, R))  # Output: 6

➢ Time Complexity: O(N^2 log N) (due to heap operations).

Keep practicing these Dynamic Programming examples and gradually develop the skills to tackle even the toughest challenges with confidence! ….🚀

Also Read: Rust for Software Development

Conclusion

Here we reached the bottom of this article! Mastering Dynamic Programming Examples takes patience and practice but once you grasp the core concepts then solving DP problems becomes much easier.

By working through these top 35 Dynamic Programming problems across different difficulty levels, you’ll develop a strong intuition for recognizing patterns and optimizing solutions efficiently.

Keep practicing, experiment with different approaches and soon DP will become one of your most valuable problem solving skills!

Thanks for reading…