Dynamic Programming Fundamentals

from typing import List, Dict, Tuple
from functools import lru_cache

def climb_stairs(n: int) -> int:
    """Count ways to climb stairs (1 or 2 steps).
    
    Time: O(n), Space: O(1)
    """
    if n <= 2:
        return n
    
    prev, curr = 1, 2
    for _ in range(3, n + 1):
        prev, curr = curr, prev + curr
    
    return curr

def house_robber(nums: List[int]) -> int:
    """Rob houses without robbing adjacent houses.
    
    Time: O(n), Space: O(1)
    """
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    prev, curr = nums[0], max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        prev, curr = curr, max(curr, prev + nums[i])
    
    return curr

def coin_change(coins: List[int], amount: int) -> int:
    """Minimum coins to make amount.
    
    Time: O(amount * len(coins)), Space: O(amount)
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
    
    return dp[amount] if dp[amount] != float('inf') else -1

def longest_common_subsequence(text1: str, text2: str) -> int:
    """Find length of longest common subsequence.
    
    Time: O(m * n), Space: O(m * n)
    """
    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]

def edit_distance(word1: str, word2: str) -> int:
    """Minimum operations to convert word1 to word2.
    
    Time: O(m * n), Space: O(m * n)
    """
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # Delete
                    dp[i][j - 1],      # Insert
                    dp[i - 1][j - 1]   # Replace
                )
    
    return dp[m][n]

Knapsack Variants

def knapsack_01(weights: List[int], values: List[int], capacity: int) -> int:
    """0/1 Knapsack problem.
    
    Time: O(n * capacity), Space: O(n * capacity)
    """
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]
            
            if weights[i - 1] <= w:
                dp[i][w] = max(
                    dp[i][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]
                )
    
    return dp[n][capacity]

def knapsack_unbounded(weights: List[int], values: List[int], capacity: int) -> int:
    """Unbounded Knapsack (items can be reused).
    
    Time: O(n * capacity), Space: O(capacity)
    """
    dp = [0] * (capacity + 1)
    
    for w in range(1, capacity + 1):
        for i in range(len(weights)):
            if weights[i] <= w:
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

def subset_sum(nums: List[int], target: int) -> bool:
    """Check if subset with given sum exists.
    
    Time: O(n * target), Space: O(target)
    """
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
    
    return dp[target]

def target_sum(nums: List[int], target: int) -> int:
    """Count ways to assign +/- to reach target.
    
    Time: O(n * sum), Space: O(sum)
    """
    total_sum = sum(nums)
    
    if (total_sum + target) % 2 != 0 or total_sum < abs(target):
        return 0
    
    subset_sum = (total_sum + target) // 2
    
    dp = [0] * (subset_sum + 1)
    dp[0] = 1
    
    for num in nums:
        for j in range(subset_sum, num - 1, -1):
            dp[j] += dp[j - num]
    
    return dp[subset_sum]

# Test cases
print(climb_stairs(5))  # 8
print(house_robber([2, 7, 9, 3, 1]))  # 12
print(coin_change([1, 5, 10, 25], 30))  # 2
print(longest_common_subsequence("abcde", "ace"))  # 3
print(edit_distance("horse", "ros"))  # 3

Backtracking

from typing import List

def subsets(nums: List[int]) -> List[List[int]]:
    """Generate all subsets.
    
    Time: O(2^n), Space: O(n)
    """
    result = []
    
    def backtrack(start: int, current: List[int]):
        result.append(current[:])
        
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    
    backtrack(0, [])
    return result

def permutations(nums: List[int]) -> List[List[int]]:
    """Generate all permutations.
    
    Time: O(n * n!), Space: O(n)
    """
    result = []
    used = [False] * len(nums)
    
    def backtrack(current: List[int]):
        if len(current) == len(nums):
            result.append(current[:])
            return
        
        for i in range(len(nums)):
            if not used[i]:
                used[i] = True
                current.append(nums[i])
                backtrack(current)
                current.pop()
                used[i] = False
    
    backtrack([])
    return result

def combination_sum(candidates: List[int], target: int) -> List[List[int]]:
    """Find combinations that sum to target (elements can repeat).
    
    Time: O(n^(target/min)), Space: O(target/min)
    """
    result = []
    
    def backtrack(start: int, current: List[int], remaining: int):
        if remaining == 0:
            result.append(current[:])
            return
        
        for i in range(start, len(candidates)):
            if candidates[i] <= remaining:
                current.append(candidates[i])
                backtrack(i, current, remaining - candidates[i])
                current.pop()
    
    backtrack(0, [], target)
    return result

def n_queens(n: int) -> List[List[str]]:
    """Solve N-Queens problem.
    
    Time: O(n!), Space: O(n^2)
    """
    result = []
    board = [['.'] * n for _ in range(n)]
    
    def is_safe(row: int, col: int) -> bool:
        # Check column
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        
        # Check diagonal (top-left)
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        
        # Check diagonal (top-right)
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j += 1
        
        return True
    
    def backtrack(row: int):
        if row == n:
            result.append([''.join(r) for r in board])
            return
        
        for col in range(n):
            if is_safe(row, col):
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'
    
    backtrack(0)
    return result

def sudoku_solve(board: List[List[str]]) -> bool:
    """Solve Sudoku puzzle.
    
    Time: O(9^(empty cells)), Space: O(1)
    """
    def is_valid(row: int, col: int, num: str) -> bool:
        # Check row
        if num in board[row]:
            return False
        
        # Check column
        if num in [board[i][col] for i in range(9)]:
            return False
        
        # Check 3x3 box
        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(box_row, box_row + 3):
            for j in range(box_col, box_col + 3):
                if board[i][j] == num:
                    return False
        
        return True
    
    def solve() -> bool:
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for num in '123456789':
                        if is_valid(i, j, num):
                            board[i][j] = num
                            if solve():
                                return True
                            board[i][j] = '.'
                    return False
        return True
    
    return solve()

# Test cases
print(subsets([1, 2, 3]))
# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

print(permutations([1, 2, 3]))
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

print(combination_sum([2, 3, 6, 7], 7))
# [[2, 2, 3], [7]]

Advanced DP Patterns

def longest_increasing_subsequence(nums: List[int]) -> int:
    """Find length of longest increasing subsequence.
    
    Time: O(n log n), Space: O(n)
    """
    import bisect
    
    tails = []
    
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    
    return len(tails)

def max_product_subarray(nums: List[int]) -> int:
    """Find maximum product subarray.
    
    Time: O(n), Space: O(1)
    """
    max_prod = min_prod = result = nums[0]
    
    for i in range(1, len(nums)):
        if nums[i] < 0:
            max_prod, min_prod = min_prod, max_prod
        
        max_prod = max(nums[i], max_prod * nums[i])
        min_prod = min(nums[i], min_prod * nums[i])
        
        result = max(result, max_prod)
    
    return result

def burst_balloons(nums: List[int]) -> int:
    """Maximum coins from bursting balloons.
    
    Time: O(n^3), Space: O(n^2)
    """
    n = len(nums)
    nums = [1] + nums + [1]
    
    dp = [[0] * (n + 2) for _ in range(n + 2)]
    
    for length in range(1, n + 1):
        for left in range(1, n - length + 2):
            right = left + length - 1
            
            for k in range(left, right + 1):
                dp[left][right] = max(
                    dp[left][right],
                    dp[left][k - 1] + nums[left - 1] * nums[k] * nums[right + 1] + dp[k + 1][right]
                )
    
    return dp[1][n]

def stone_game(piles: List[int]) -> bool:
    """Determine if first player can win stone game.
    
    Time: O(n^2), Space: O(n^2)
    """
    n = len(piles)
    dp = [[0] * n for _ in range(n)]
    
    for i in range(n):
        dp[i][i] = piles[i]
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(
                piles[i] - dp[i + 1][j],
                piles[j] - dp[i][j - 1]
            )
    
    return dp[0][n - 1] > 0

# Test cases
print(longest_increasing_subsequence([10, 9, 2, 5, 3, 7, 101, 18]))  # 4
print(max_product_subarray([2, 3, -2, 4]))  # 6
print(stone_game([5, 3, 4, 5]))  # True

Follow-Up Questions

1. How do you optimize space in dynamic programming problems?

2. Explain the difference between top-down and bottom-up DP.

3. When would you use memoization vs tabulation?

4. How do you handle problems with multiple constraints?

5. Explain the concept of state compression in DP.