def dpTopDown(n: int) -> int:
    """
    Top-down DP with memoization.
    Time: O(n), Space: O(n)
    """
    memo = {}
    
    def dp(i: int) -> int:
        # Base case
        if i <= 0:
            return BASE_VALUE
        
        # Check cache
        if i in memo:
            return memo[i]
        
        # Recurrence relation
        memo[i] = RECURRENCE_FORMULA
        
        return memo[i]
    
    return dp(n)

def dpBottomUp(n: int) -> int:
    """
    Bottom-up DP with tabulation.
    Time: O(n), Space: O(n)
    """
    if n <= 0:
        return BASE_VALUE
    
    # Initialize DP table
    dp = [0] * (n + 1)
    dp[0] = BASE_VALUE_0
    dp[1] = BASE_VALUE_1
    
    # Fill table
    for i in range(2, n + 1):
        dp[i] = RECURRENCE_FORMULA
    
    return dp[n]

def maxProfit(prices: List[int]) -> int:
    """
    Find maximum profit with single transaction.
    Time: O(n), Space: O(1)
    """
    min_price = float('inf')
    max_profit = 0
    
    for price in prices:
        # Track minimum price seen so far
        min_price = min(min_price, price)
        # Calculate profit if selling today
        profit = price - min_price
        # Update maximum profit
        max_profit = max(max_profit, profit)
    
    return max_profit

def wordBreak(s: str, wordDict: List[str]) -> bool:
    """
    Check if string can be segmented into dictionary words.
    Time: O(n^2 * m), Space: O(n)
    n = len(s), m = avg word length
    """
    word_set = set(wordDict)
    n = len(s)
    
    # dp[i] = can segment s[0:i]
    dp = [False] * (n + 1)
    dp[0] = True  # Empty string
    
    for i in range(1, n + 1):
        for j in range(i):
            # If s[0:j] can be segmented and s[j:i] is a word
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    
    return dp[n]

def maxSubArray(nums: List[int]) -> int:
    """
    Find maximum sum contiguous subarray.
    Time: O(n), Space: O(1)
    """
    max_sum = nums[0]
    current_sum = nums[0]
    
    for num in nums[1:]:
        # Either extend current subarray or start new
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    
    return max_sum

def maxProfit(prices: List[int]) -> int:
    """
    Maximum profit with at most 2 transactions.
    Time: O(n), Space: O(1)
    """
    # State machine: track best profit at each state
    buy1 = buy2 = float('-inf')
    sell1 = sell2 = 0
    
    for price in prices:
        # First transaction
        buy1 = max(buy1, -price)
        sell1 = max(sell1, buy1 + price)
        
        # Second transaction (can only start after first sells)
        buy2 = max(buy2, sell1 - price)
        sell2 = max(sell2, buy2 + price)
    
    return sell2

# State: dp[i] = ways to reach step i
# Recurrence: dp[i] = dp[i-1] + dp[i-2]

# State: dp[i] = max money robbing up to house i
# Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i])

# State: dp[i] = length of LIS ending at i
# Recurrence: dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]

# State: dp[i] = min coins to make amount i
# Recurrence: dp[i] = min(dp[i - coin] + 1) for all coins

# State: dp[i][j] = min ops to convert s1[0:i] to s2[0:j]
# Recurrence: if s1[i] == s2[j]: dp[i-1][j-1]
#             else: 1 + min(insert, delete, replace)

def maxProfitWithCooldown(prices: List[int]) -> int:
    """
    Stock with cooldown - state machine DP.
    States: held, sold, cooldown
    """
    held = float('-inf')
    sold = 0
    cooldown = 0
    
    for price in prices:
        prev_sold = sold
        
        # Can sell if currently holding
        sold = held + price
        
        # Can buy if in cooldown, or stay held
        held = max(held, cooldown - price)
        
        # Enter cooldown after selling
        cooldown = max(cooldown, prev_sold)
    
    return max(sold, cooldown)

def countDigitOne(n: int) -> int:
    """
    Count digit 1 in range [1, n] using digit DP.
    Time: O(log n), Space: O(log n)
    """
    # Complex pattern - build numbers digit by digit
    # Track: position, count of 1s, tight bound

def shortestPathVisitingAllNodes(graph: List[List[int]]) -> int:
    """
    Visit all nodes in graph - bitmask DP.
    State: (node, visited_mask)
    """
    # Use bitmask to represent set of visited nodes
    # dp[(node, mask)] = min steps to reach node with mask visited

# Original: O(n) space
def fib(n: int) -> int:
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# Optimized: O(1) space
def fib(n: int) -> int:
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    return prev1