Dynamic Programming Patterns

Dynamic Programming (DP) is a powerful algorithmic technique used to solve a wide range of optimization problems. It's a cornerstone of technical interviews, and LeetCode provides an extensive collection of DP problems to help you master this crucial skill. In this comprehensive guide, we'll explore LeetCode's top DP problems, dissecting their statements, approaches, solution strategies (Top-Down and Bottom-Up), and identifying similar problems across various DP patterns.

Minimum Cost Climbing Stairs (Problem #746)

Problem Statement: You are given an array cost where cost[i] represents the cost of climbing the i-th stair. You can start climbing from either the 0-th or 1-st stair. Each time you can either climb one or two steps. Return the minimum cost to reach the top of the floor.

Approach:
This problem exhibits a classic Dynamic Programming pattern where the minimum cost to reach a stair is the minimum of the costs of reaching the previous two stairs plus the cost of the current stair.

Top-Down Approach (Recursive with Memoization):

We define a recursive function minCostClimbingStairsTopDown, which takes the current index n and the array cost as inputs.
Within this function, we recursively call itself for the previous two stairs (if they exist) and memoize the results to avoid redundant calculations.
Finally, we return the minimum cost to reach the n-th stair.

def minCostClimbingStairsTopDown(cost, n, memo):
    if n <= 1:
        return cost[n]
    if memo[n] != -1:
        return memo[n]
    memo[n] = min(minCostClimbingStairsTopDown(cost, n-1, memo), minCostClimbingStairsTopDown(cost, n-2, memo)) + cost[n]
    return memo[n]

def minCostClimbingStairs(cost):
    n = len(cost)
    memo = [-1] * n
    return min(minCostClimbingStairsTopDown(cost, n-1, memo), minCostClimbingStairsTopDown(cost, n-2, memo))

Bottom-Up Approach (Iterative):

We initialize a DP array dp of size n+1 to store the minimum cost to reach each stair.
We start by assigning the costs of the first two stairs to the first two elements of the DP array.
Then, we iterate through the remaining stairs and compute the minimum cost to reach each stair by considering the minimum of the costs of the previous two stairs plus the cost of the current stair.
Finally, we return the minimum cost to reach either the last or second last stair, as these are the possible starting points.

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

Example Usage:

cost = [10, 15, 20]
print(minCostClimbingStairsBottomUp(cost))  # Output: 15

Similar Problems:

Problem 70: Climbing Stairs - Given n stairs, you can climb 1 or 2 steps at a time. Determine the number of distinct ways to reach the top.

Top-Down Approach (Recursive with Memoization):

def climbStairsTopDown(n, memo):
if n <= 1:
    return 1
if memo[n] != -1:
    return memo[n]
memo[n] = climbStairsTopDown(n-1, memo) + climbStairsTopDown(n-2, memo)
return memo[n]

def climbStairs(n):
memo = [-1] * (n + 1)
return climbStairsTopDown(n, memo)

Bottom-Up Approach (Iterative):

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

Problem 322: Coin Change - Given an amount n and a list of coin denominations, determine the minimum number of coins needed to make up that amount.

Top-Down Approach (Recursive with Memoization):

def coinChangeTopDown(coins, amount, memo):
if amount < 0:
    return -1
if amount == 0:
    return 0
if memo[amount] != float('inf'):
    return memo[amount]
for coin in coins:
    subproblem = coinChangeTopDown(coins, amount - coin, memo)
    if subproblem >= 0:
        memo[amount] = min(memo[amount], 1 + subproblem)
return memo[amount] if memo[amount] != float('inf') else -1

def coinChange(coins, amount):
memo = [float('inf')] * (amount + 1)
return coinChangeTopDown(coins, amount, memo)

Analysis:

Both the Top-Down and Bottom-Up approaches have a time complexity of O(n) and a space complexity of O(n), where n is the number of stairs.
These approaches efficiently compute the minimum cost to reach the top of the stairs by considering the optimal substructure property of the problem.

Merging Intervals

Problem Statement: Given a collection of intervals, merge all overlapping intervals.

Approach:
The key to solving merging interval problems lies in identifying the optimal solution for each interval by considering the best from the left and right sides, then merging them as necessary.

Top-Down Approach (Recursive with Memoization):

We define a recursive function mergeIntervalsTopDown, which takes the collection of intervals intervals, the start index start, the end index end, and a memoization table memo.
Within this function, we recursively call itself for different partitions of the intervals and memoize the results to avoid redundant calculations.
Finally, we return the merged intervals for the given range.

def mergeIntervalsTopDown(intervals, start, end, memo):
    if start == end:
        return intervals[start][0], intervals[start][1]
    if memo[start][end]:
        return memo[start][end]
    for i in range(start, end):
        left_start, left_end = mergeIntervalsTopDown(intervals, start, i, memo)
        right_start, right_end = mergeIntervalsTopDown(intervals, i+1, end, memo)
        if left_end >= right_start:
            memo[start][end] = left_start, right_end
            return memo[start][end]
    memo[start][end] = intervals[start][0], intervals[end][1]
    return memo[start][end]

def merge(intervals):
    n = len(intervals)
    if n == 0:
        return []
    memo = [[None]*n for _ in range(n)]
    return mergeIntervalsTopDown(intervals, 0, n-1, memo)

Bottom-Up Approach (Iterative):

We start by sorting the intervals based on the start times.
Then, we initialize an empty list merged to store the merged intervals.
We iterate through the sorted intervals and merge overlapping intervals by comparing the start and end times.
Finally, we return the list of merged intervals.

def mergeIntervalsBottomUp(intervals):
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or interval[0] > merged[-1][1]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

Example Usage:

intervals = [[1,3],[2,6],[8,10],[15,18]]
print(merge(intervals))  # Output: [[1,6],[8,10],[15,18]]

Similar Problems:

Problem 57: Insert Interval - Given a set of non-overlapping intervals sorted by their start times, insert a new interval into the intervals (merge if necessary).

Top-Down Approach:

def insertInterval(intervals, newInterval):
    merged = []
    i = 0
    while i < len(intervals) and intervals[i][1] < newInterval[0]:
        merged.append(intervals[i])
        i += 1
    while i < len(intervals) and intervals[i][0] <= newInterval[1]:
        newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]
        i += 1
    merged.append(newInterval)
    merged.extend(intervals[i:])
    return merged

Bottom-Up Approach:

def insertInterval(intervals, newInterval):
    merged = []
    i = 0
    while i < len(intervals) and intervals[i][1] < newInterval[0]:
        merged.append(intervals[i])
        i += 1
    while i < len(intervals) and intervals[i][0] <= newInterval[1]:
        newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]
        i += 1
    merged.append(newInterval)
    merged.extend(intervals[i:])
    return merged

Problem 253: Meeting Rooms II - Given an array of meeting time intervals, determine the minimum number of conference rooms required.

Top-Down Approach:

import heapq

def minMeetingRooms(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])
    rooms = []
    heapq.heappush(rooms, intervals[0][1])
    for interval in intervals[1:]:
        if interval[0] >= rooms[0]:
            heapq.heappop(rooms)
        heapq.heappush(rooms, interval[1])
    return len(rooms)

Bottom-Up Approach:

import heapq

def minMeetingRooms(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])
    rooms = []
    heapq.heappush(rooms, intervals[0][1])
    for interval in intervals[1:]:
        if interval[0] >= rooms[0]:
            heapq.heappop(rooms)
        heapq.heappush(rooms, interval[1])
    return len(rooms)

Analysis:

The Top-Down approach has a time complexity of O(n^2) and a space complexity of O(n^2) due to the memoization table.

The Bottom-Up approach has a time complexity of O(n log n) and a space complexity of O(n) due to the sorting of intervals.

Both approaches efficiently merge overlapping intervals while considering the optimal substructure property of the problem.

Dynamic Programming on Strings

Problem Statement: Dynamic Programming on strings involves solving problems that require processing or comparing strings optimally.

Approach:
Most problems in this category involve building a 2D DP table to store intermediate results, where the value at dp[i][j] represents the optimal solution considering substrings s1[:i] and s2[:j].

Example Problem: Longest Common Subsequence (Problem #1143)

Problem Statement: Given two strings text1 and text2, return the length of their longest common subsequence.

Approach:
We build a 2D DP table dp where dp[i][j] represents the length of the longest common subsequence of text1[:i] and text2[:j].

If text1[i-1] == text2[j-1], we extend the common subsequence by 1: dp[i][j] = dp[i-1][j-1] + 1.
Otherwise, we take the maximum length of common subsequences from either deleting a character from text1 or text2: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Similar Problems:

Problem 516: Longest Palindromic Subsequence - Given a string s, find the length of the longest palindromic subsequence in s.
Problem 72: Edit Distance - Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

Code Implementation:

def longestCommonSubsequence(text1: str, text2: str) -> int:
    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]

Example Usage:

text1 = "abcde"
text2 = "ace"
print(longestCommonSubsequence(text1, text2))  # Output: 3 (LCS: "ace")

Analysis:

The time complexity of the DP solution is O(m * n), where m and n are the lengths of text1 and text2, respectively.
The space complexity is also O(m * n) due to the DP table.
This approach efficiently finds the longest common subsequence between two strings by leveraging dynamic programming techniques.

Decision Making

Problem Statement: Decision-making problems involve determining whether to include or exclude the current state to optimize a given objective.

Approach:
These problems usually involve constructing a DP table where dp[i][j] represents the maximum value or minimum cost achievable up to the i-th state by considering j options.

Example Problem: House Robber (Problem #198)

Problem Statement: You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, and the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected, and it will automatically contact the police if two adjacent houses were broken into on the same night. Determine the maximum amount of money you can rob tonight without alerting the police.

Approach:
We use a DP approach to calculate the maximum amount of money that can be robbed up to the i-th house while considering two options: either robbing the current house or skipping it.

If we choose to rob the i-th house, we add its value to the maximum loot from the previous non-adjacent house.
If we choose to skip the i-th house, we take the maximum loot up to the i-1-th house.

Similar Problems:

Problem 213: House Robber II - Similar to Problem #198, but the houses are arranged in a circular manner.
Problem 121: Best Time to Buy and Sell Stock - Given an array of stock prices, find the maximum profit that can be obtained by buying and selling at most once.

House Robber II (Problem #213)

Problem Statement: Similar to Problem #198, but the houses are arranged in a circular manner.

Approach:
To solve this problem, we can use dynamic programming to find the maximum loot that can be obtained while considering two cases:

Robbing the houses from the first to the second-to-last house.
Robbing the houses from the second to the last house.

We then return the maximum loot obtained from these two cases.

Top-Down Approach:

def rob(nums):
    if len(nums) == 1:
        return nums[0]
    return max(robHelper(nums[:-1]), robHelper(nums[1:]))

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

Bottom-Up Approach:

def rob(nums):
    if len(nums) == 1:
        return nums[0]
    return max(robHelper(nums[:-1]), robHelper(nums[1:]))

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

Similar Problems:

Problem 198: House Robber - You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed.
Problem 337: House Robber III - The third problem in the house robber series, where houses are arranged in a binary tree.

Best Time to Buy and Sell Stock (Problem #121)

Problem Statement: Given an array of stock prices, find the maximum profit that can be obtained by buying and selling at most once.

Approach:
To solve this problem, we can use dynamic programming to keep track of the maximum profit that can be obtained by buying and selling the stock at each day.

Top-Down Approach:

def maxProfit(prices):
    def helper(index, bought):
    if index >= len(prices):
        return 0
    if (index, bought) in memo:
        return memo[(index, bought)]

    if bought:
        # If currently holding a stock, we can either sell it or skip this day
        sell_today = prices[index] + helper(index + 1, False)
        skip_today = helper(index + 1, True)
        memo[(index, bought)] = max(sell_today, skip_today)
    else:
        # If not holding a stock, we can either buy a stock or skip this day
        buy_today = -prices[index] + helper(index + 1, True)
        skip_today = helper(index + 1, False)
        memo[(index, bought)] = max(buy_today, skip_today)
    
    return memo[(index, bought)]

if not prices:
    return 0

memo = {}
return helper(0, False)

Example usage:

prices = [7, 1, 5, 3, 6, 4]
print(maxProfit(prices)) # Output should be 5

Bottom-Up Approach:

def maxProfit(prices):
    if not prices:
        return 0
    max_profit = 0
    min_price = prices[0]
    for price in prices[1:]:
        max_profit = max(max_profit, price - min_price)
        min_price = min(min_price, price)
    return max_profit

Similar Problems:

Problem 122: Best Time to Buy and Sell Stock II - You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Problem 123: Best Time to Buy and Sell Stock III - You may complete at most two transactions.

Code Implementation:

def rob(nums: List[int]) -> int:
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]
    
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    
    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    
    return dp[-1]

Example Usage:

nums = [2,7,9,3,1]
print(rob(nums))  # Output: 12 (Rob houses 1, 3, and 5 for a total of 12)

Analysis:

The time complexity of the DP solution is O(n), where n is the number of houses.
The space complexity is O(n) due to the DP array.
This approach efficiently determines the maximum loot that can be obtained without alerting the police by employing dynamic programming principles.

Comments (24)