Multidimensional DP

Advanced DP problems may require 3D or higher dimensional state spaces.

3D DP Example: Best Time to Buy/Sell Stock III

Problem: At most 2 transactions allowed.

def maxProfit(prices):
    """Max profit with at most 2 transactions"""
    if not prices:
        return 0

    # dp[i][k][s]
    # i = day, k = transactions remaining, s = 0 (no stock) or 1 (holding stock)

    # Simplified: track states directly
    buy1 = buy2 = float('-inf')
    sell1 = sell2 = 0

    for price in prices:
        buy1 = max(buy1, -price)
        sell1 = max(sell1, buy1 + price)
        buy2 = max(buy2, sell1 - price)
        sell2 = max(sell2, buy2 + price)

    return sell2

State Machine DP

Model as transitions between states.

def maxProfit(prices, fee):
    """With transaction fee"""
    cash = 0
    hold = -prices[0]

    for price in prices[1:]:
        cash = max(cash, hold + price - fee)
        hold = max(hold, cash - price)

    return cash

DP with Bitmask

Use bitmask to represent states.

def shortestPathLength(graph):
    """Shortest path visiting all nodes"""
    n = len(graph)
    queue = [(1 << i, i) for i in range(n)]
    dist = {(1 << i, i): 0 for i in range(n)}

    while queue:
        mask, node = queue.pop(0)

        if mask == (1 << n) - 1:
            return dist[(mask, node)]

        for neighbor in graph[node]:
            new_mask = mask | (1 << neighbor)
            if (new_mask, neighbor) not in dist:
                dist[(new_mask, neighbor)] = dist[(mask, node)] + 1
                queue.append((new_mask, neighbor))

    return -1

Key Takeaway

Advanced DP extends the same principles to higher dimensions or more complex state representations. The core approach remains: define state, find recurrence, build solution.