DP Optimization Techniques

Space Optimization

Rolling Array

Only keep last few rows/columns.

def uniquePaths(m, n):
    """Space-optimized grid DP"""
    # Only need previous row
    dp = [1] * n

    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j-1]

    return dp[n-1]

Two Variables

For Fibonacci-like problems.

def climbStairs(n):
    """O(1) space"""
    if n <= 2:
        return n

    prev2, prev1 = 1, 2
    for i in range(3, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current

    return prev1

Time Optimization

Binary Search + DP

For Longest Increasing Subsequence.

def lengthOfLIS(nums):
    """O(n log n) solution"""
    from bisect import bisect_left

    dp = []

    for num in nums:
        pos = bisect_left(dp, num)
        if pos == len(dp):
            dp.append(num)
        else:
            dp[pos] = num

    return len(dp)

Monotonic Queue Optimization

For sliding window DP.

from collections import deque

def maxResult(nums, k):
    """Jump game with max score"""
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    dq = deque([0])

    for i in range(1, n):
        # Remove out of range
        while dq and dq[0] < i - k:
            dq.popleft()

        # Best previous position
        dp[i] = nums[i] + dp[dq[0]]

        # Maintain decreasing queue
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        dq.append(i)

    return dp[n-1]

Key Takeaway

Optimization is about recognizing what information you actually need and using appropriate data structures to access it efficiently.