Dynamic Programming — Patterns (Part III)

Patterns and examples with solution

Part I | Part II | Part III | Part IV | Part V | Part VI

We will discuss the following three patterns.

• Kadane’s Algo
• Matrix Chain Multiplication
• Count Distinct Ways

Kadane’s Algo

Kadane’s Algorithm is primarily used for solving the Maximum Subarray Problem and its variations where the problem asks to optimize a contiguous subarray within a one-dimensional numeric array. The key concept in Kadane’s Algorithm is “localMaxSum,” which represents the maximum sum of a contiguous subarray ending at a specific index. By keeping track of this “local” maximum, we can efficiently find the “global” maximum sum across the entire array.

• LC 121. Best Time to Buy and Sell Stock

Let us see the brute force approach first. In this approach, we try every possible buy-sell pair and calculate the profit for each, keeping track of the maximum.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        for i in range(len(prices)):  # Buy day
            for j in range(i + 1, len(prices)): # Sell day
                profit = prices[j] - prices[i]
                if profit > 0: # Only consider positive profits
                    max_profit = max(max_profit, profit)
        return max_profit

The brute force recalculates profits repeatedly. What if we could use past information to avoid rechecking every pair? For each day, we could track the minimum price seen so far (best buy price) and compute the maximum profit if we sell on that day.

dp[i] represents the maximum profit if we sell on day i.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0
        # dp[i] = max profit if we sell on day i
        dp = [0] * len(prices)
        min_price = prices[0]  # Minimum price seen so far
        
        for i in range(1, len(prices)):
            # Profit if we sell at i using the min price so far
            dp[i] = max(0, prices[i] - min_price)
            # Update min_price if current price is lower
            min_price = min(min_price, prices[i])
        
        # Return the maximum profit from all possible sell days
        return max(dp)

Memory optimization by removing the dp array.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0
        max_profit = 0
        min_price = prices[0]
        
        for i in range(1, len(prices)):
            if prices[i] > min_price:
                current_profit = prices[i] - min_price
                max_profit = max(max_profit, current_profit)
            min_price = min(min_price, prices[i])
        
        return max_profit

We can even optimize it further. We can separate the decision to update the buy price (cur_cp) from the profit calculation, making the code read like a natural progression: “If I can sell for profit, do it; otherwise, reset my buy point.”

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        cur_cp = prices[0]  # Current cheapest price (buy price)
        for i in range(1, len(prices)):
            if cur_cp < prices[i]:
                res = max(res, prices[i] - cur_cp)
            else:
                cur_cp = prices[i]
        return res

• LeetCode 53: Maximum Subarray

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        max_so_far = float('-inf')
        max_ending_here = 0

        for i in range(len(nums)):
            max_ending_here += nums[i]

            if (max_so_far < max_ending_here):
                max_so_far = max_ending_here

            if (max_ending_here < 0):
                max_ending_here = 0

        return max_so_far

• LeetCode 918: Maximum Sum Circular Subarray

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        global_min, global_max = nums[0],nums[0]
        curr_min, curr_max = 0,0
        total = 0

        for num in nums:
            curr_min = min(curr_min, 0) + num
            global_min = min(global_min, curr_min)

            curr_max = max(curr_max,0)+num
            global_max = max(global_max, curr_max)
            total += num

        return global_max if global_max<0 else max(total-global_min, global_max)

• LeetCode 152: Maximum Product Subarray

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        cur_max = cur_min = res = nums[0]
        for num in nums[1:]:
            if num<0:
                cur_max, cur_min = cur_min, cur_max
            
            cur_max = max(num, cur_max * num)
            cur_min = min(num, cur_min * num)

            res = max(res, cur_max)
            
        return res

Matrix Chain Multiplication

In matrix chain multiplication, we minimize the cost of multiplying matrices A[i] to A[j] by choosing a split point k. The MCM pattern generalizes the idea of optimizing a sequence of operations where each operation’s cost depends on its neighbors, and the sequence can be split recursively into subproblems.

• LC 312. Burst Balloons

Brute force code

def maxCoins(nums):
    nums = [1] + nums + [1]  # Add boundary balloons
    def burst(left, right):
        if left > right:  # No balloons to burst
            return 0
        max_coins = 0
        for k in range(left, right + 1):
            coins = nums[left - 1] * nums[k] * nums[right + 1]
            coins += burst(left, k - 1) + burst(k + 1, right)
            max_coins = max(max_coins, coins)
        return max_coins
    return burst(1, len(nums) - 2)

This will have an exponential time complexity. So we add memoization to improve code execution time.

def maxCoins(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    memo = {}
    
    def burst(left, right):
        if left > right:
            return 0
        if (left, right) in memo:
            return memo[(left, right)]
        max_coins = 0
        for k in range(left, right + 1):
            coins = nums[left - 1] * nums[k] * nums[right + 1]
            coins += burst(left, k - 1) + burst(k + 1, right)
            max_coins = max(max_coins, coins)
        memo[(left, right)] = max_coins
        return max_coins
    
    return burst(1, n - 2)

In MCM-style problems, we typically build solutions from smaller subproblems to larger ones. Here, “smaller” means shorter subarrays (fewer balloons between left and right). The key insight is to define dp[left][right] as the maximum coins obtainable by bursting all balloons from index left to right, assuming nums[left-1] and nums[right+1] are the boundary balloons still present.

Intuition

• Subproblem Size: Start with subarrays of length 1 (one balloon), then 2, up to n-2 (all balloons except boundaries).
• Last Balloon Burst: For a range [left, right], assume balloon k is burst last. The coins earned are nums[left-1] * nums[k] * nums[right+1], plus the coins from subproblems [left, k-1] and [k+1, right], which are already solved.
• Maximization: Try all possible k and take the max.

DP Array: dp[left][right] is the max coins for bursting balloons from left to right.

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]  # Add boundary balloons
        n = len(nums)
        dp = [[0] * n for _ in range(n)]  # dp[left][right] = max coins
        
        for length in range(1, n - 1):  # Length of subarray
            for left in range(1, n - length):  # Start index
                right = left + length - 1  # End index
                for k in range(left, right + 1):  # Last balloon to burst
                    coins = nums[left - 1] * nums[k] * nums[right + 1]
                    coins += dp[left][k - 1] + dp[k + 1][right]
                    dp[left][right] = max(dp[left][right], coins)
        
        return dp[1][n - 2]  # Answer for entire array

Template for an MCM solution

def solveMCM(sequence):
    n = len(sequence)  # Length of the sequence
    dp = [[0] * n for _ in range(n)]  # dp[i][j] = optimal value for subsequence i to j
    
    # Loop over subproblem lengths (from 1 to n-1 or n, depending on problem)
    for length in range(1, n):  # Adjust range based on problem (e.g., n-1 for balloons)
        # Loop over starting index i
        for i in range(n - length):  # Adjust starting point if boundaries are padded
            j = i + length - 1  # Ending index
            
            # Initialize dp[i][j] (for min, use infinity; for max, use 0)
            dp[i][j] = float('inf')  # For minimization (change to 0 for maximization)
            
            # Try all possible split points k between i and j
            for k in range(i, j + 1):
                # Calculate cost/value for splitting at k
                # General form: cost = boundary_cost(i, k, j) + dp[i][k-1] + dp[k+1][j]
                cost = (boundary_cost(sequence, i, k, j) + 
                        (dp[i][k-1] if k > i else 0) + 
                        (dp[k+1][j] if k < j else 0))
                
                # Update dp[i][j] based on optimization goal
                dp[i][j] = min(dp[i][j], cost)  # For minimization (use max for maximization)
    
    return dp[0][n-1]  # Adjust indices based on problem definition

# Helper function for boundary cost (problem-specific)
def boundary_cost(sequence, i, k, j):
    # Example for MCM: return sequence[i-1] * sequence[k] * sequence[j]
    # Define based on problem
    pass

• LC 1000. Minimum Cost to Merge Stones

This problem has the following features that make it solvable through MCM

• It involves a sequence (stones) that must be processed optimally.
• It requires partitioning to break the problem into subproblems (dp[i][t] and dp[t+1][j]).
• The cost depends on the range being merged (via accum), similar to MCM’s boundary-dependent cost.
• We can build the solution bottom-up, iterating over lengths and split points.

class Solution:
    def mergeStones(self, stones: List[int], k: int) -> int:
        n = len(stones)
        if (n-1) % (k-1) != 0:
            return -1
        accum = [0] + list(itertools.accumulate(stones))

        dp = [[0]*n for _ in range(n)]
        for l in range(k, n+1):
            for i in range(n-l+1):
                j = i + l - 1
                if l > k:
                    dp[i][j] = min([dp[i][t] + dp[t+1][j] for t in range(i, j, k-1)])
                if (l-1)%(k-1) == 0:
                    dp[i][j] += accum[j+1] - accum[i]

        return dp[0][n-1]

• LC 1039. Minimum Score Triangulation of Polygon

This problem can be solved by partitioning the main problem into smaller sub-problems. We can take any two adjacent vertices and one more vertex from the remaining ones and create a triangle, this will split the original shape into three parts, one triangle, and two other smaller versions of the same problem.

Here,

• dp[left][right] represents the minimum score to triangulate the sub-polygon from vertex left to vertex right (inclusive).
• Split Point k: For each k between left and right, form a triangle (left, k, right) and recursively solve the sub-polygons (left, k) and (k, right).

Base Case

• For l < 2 (subarrays of length 1 or 2), dp[left][right] = 0 implicitly, as no triangulation is possible (fewer than 3 vertices). The loop starts at l = 2, so these remain 0.

class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int:
        n = len(values)
        dp = [[0]*n for _ in range(n)]
        for l in range(2, n):
            for left in range(0, n - l):
                right = left + l
                dp[left][right] = math.inf
                for k in range(left + 1, right):
                    cost = dp[left][k] + dp[k][right] + values[left]*values[right]*values[k]
                    dp[left][right] = min(dp[left][right], cost)
        return dp[0][-1]

• LC 546. Remove Boxes

class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        n = len(boxes)

        dp = [[[0] * (n+1)  for _ in range(n+1)] for _ in range(n+1)]
        
        # dp[l][r][k] represents the maximum points for removing all boxes in the subarray boxes[l...r] where k represents how many boxes of the same color as boxes[l] have already been grouped to the left.

        for length in range(1, n+1):
            for l in range (n + 1 - length):
                r = l + length - 1
                for k in range(l+1):
                    if l + 1 <= r:
                        res = (k + 1) * (k + 1) + dp[l + 1][r][0]
                    else:
                        res = (k + 1) * (k + 1)
                    
                    for m in range(l+1, r+1):
                        if (boxes[m] == boxes[l]):
                            res = max(res, dp[l + 1][m - 1][0] + dp[m][r][k + 1])
                    
                    dp[l][r][k] = res

        return dp[0][n-1][0]

Count Distinct Ways

This pattern is useful when:

1. You need to count the number of different ways to achieve a certain goal or reach a particular state.
2. The problem involves making a series of choices or steps to reach a target.
3. There are multiple valid paths or combinations to reach the solution.
4. The problem can be broken down into smaller subproblems with overlapping solutions.
5. You’re dealing with combinatorial problems that ask “in how many ways” can something be done.

• LC 91. Decode Ways

class Solution:
    def numDecodings(self, s: str) -> int:
        '''
        There are 2 states 
        - one where we didnt interact with the part we need to change
        - second we have already interacted with the first digit of the 2 digit part 
        
        final ans will be sum of both states
        '''
        res , state1, state2 = 1, 1, 1
        if s[0] == '0':
            return 0
        n = len(s)
        for i in range(1, n):
            state2, state1 = state1, res
            if(s[i]=='0' and s[i-1]>='3'):
                return 0
            if(s[i]=='0' and s[i-1]<='0'):
                return 0
            if(s[i]<='9' and s[i-1]=='1'):
                res = state1 + state2
            if (s[i]<='6' and s[i-1]=='2'):
                res = state1 + state2
            if s[i]=='0':
                res = state2
        return res

• LC 2266. Count Number of Texts

class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        keys = set(['2','22','222','3','33','333','4','44','444','5','55','555','6','66','666','7','77','777','7777','8','88','888','9','99','999','9999'])
        n = len(pressedKeys)+1

        dp = [0]*n
        dp[0] = 1 
        MOD = 1000000007

        for end in range(1, n):
            for begin in range(end-1,-1,-1):
                if pressedKeys[begin:end] not in keys:
                    break
                dp[end] = (dp[end] + dp[begin]) % 1000000007
        return dp[n-1]