Reconhecendo DP: Subproblemas Sobrepostos

O que é programação dinâmica

# Two ingredients of DP:
# 1. Overlapping sub-problems:
#    fib(5) -> fib(4) + fib(3)
#    fib(4) -> fib(3) + fib(2)  <- fib(3) computed twice!
#    Without caching: O(2^n) calls for Fibonacci

# 2. Optimal substructure:
#    Shortest path from A to C through B:
#    shortest(A,C) = shortest(A,B) + shortest(B,C)
#    The sub-path A->B must itself be the shortest

# Contrast with greedy: greedy makes one locally optimal
# choice; DP tries all choices and picks the best.
print('DP = overlapping sub-problems + optimal substructure')

Fibonacci: o ponto de entrada clássico para DP

import time

def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)

# Count the calls:
call_count = [0]
def fib_count(n):
    call_count[0] += 1
    if n <= 1: return n
    return fib_count(n-1) + fib_count(n-2)

fib_count(10)
print(f'Calls for fib(10): {call_count[0]}')  # 177 calls for n=10!

call_count[0] = 0
fib_count(20)
print(f'Calls for fib(20): {call_count[0]}')  # 21891 calls
# n=30 -> ~2.7 million calls: exponential growth

Visualizando a árvore de recursão

# fib(5) recursion tree (simplified):
#                fib(5)
#               /       \
#           fib(4)     fib(3)
#           /    \     /    \
#       fib(3) fib(2) fib(2) fib(1)
#       /   \       \       
#   fib(2) fib(1) fib(1)   
#   /   \
# fib(1) fib(0)

# fib(3) appears TWICE
# fib(2) appears THREE TIMES
# Each redundant call wastes exponential time

# Key insight: fib(n) only has O(n) DISTINCT sub-problems
# (fib(0), fib(1), ..., fib(n))
# DP computes each ONCE -> O(n) total
print('Distinct sub-problems: O(n) but naive calls: O(2^n)')

Identificando subproblemas sobrepostos

# DP signal phrases in problem statements:
# 'minimum number of coins to make amount X'
# 'maximum profit from stock trades'
# 'number of ways to climb n stairs'
# 'can you reach the last index?'
# 'longest common subsequence'
# 'edit distance between two strings'

# All have this shape:
# solve(input) = f(solve(smaller_input_1), solve(smaller_input_2), ...)
# And multiple branches end up calling solve with the same argument.

# If the recursion tree has repeated nodes: DP
# If subproblems are all independent: divide-and-conquer (no DP needed)
print('Repeated arguments in recursion tree -> DP')

Estrutura ótima explicada

# Optimal substructure examples:

# SHORTEST PATH: shortest(A,C) = min over all B: shortest(A,B) + w(B,C)
# -> Sub-paths must be optimal: YES, has optimal substructure

# LONGEST PATH (no cycles, DAG): can also use DP
# -> Longer path through node B means sub-path A->B must be longest

# LONGEST PATH (with cycles): NO optimal substructure
# -> Best path from A to C might reuse nodes: sub-problems not independent

# COIN CHANGE: min coins for amount n = 1 + min(min coins for n-coin_i)
# -> YES: optimal for n-coin_i is needed for optimal n

print('Optimal substructure: build global optimum from local optima')

Subindo escadas: sua primeira DP

def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1  # 1 way to reach step 1
    dp[2] = 2  # 2 ways to reach step 2: (1+1) or (2)
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]  # come from i-1 or i-2
    return dp[n]

for n in range(1, 8):
    print(f'climb_stairs({n}) = {climb_stairs(n)}')
# 1, 2, 3, 5, 8, 13, 21 -- Fibonacci sequence!

A estrutura de DP: definir, formular a recorrência, ordenar

# Framework applied to climbing stairs:
# Step 1 - Define state:
#   dp[i] = number of distinct ways to reach step i
# Step 2 - Recurrence:
#   dp[i] = dp[i-1] + dp[i-2]  (come from step i-1 or i-2)
# Step 3 - Fill order:
#   Compute dp[1], dp[2], dp[3], ..., dp[n] in order
#   Because dp[i] depends on dp[i-1] and dp[i-2] (smaller)
# Base cases: dp[1]=1, dp[2]=2

# Framework applied to coin change:
# Step 1: dp[amount] = minimum coins to make that amount
# Step 2: dp[i] = 1 + min(dp[i-coin] for coin in coins if i >= coin)
# Step 3: Fill i from 1 to amount
# Base: dp[0] = 0 (zero coins for zero amount)
print('DP framework: define state -> recurrence -> fill order')

Quando NOT usar DP

# DP vs alternatives:
# Problem: can you jump to the end of the array?
#   Greedy: track max reachable index -> O(n) O(1) BETTER than DP
# Problem: shortest path unweighted graph?
#   BFS: O(V+E) BETTER than DP on general graph
# Problem: sort an array?
#   Comparison sort: O(n log n), no DP needed

# DP IS the right choice when:
# - Greedy fails (choices interact)
# - Need to count/enumerate all possibilities
# - Problem has 'how many ways' or 'minimum/maximum' flavor
# - Recursion tree clearly shows overlapping sub-problems
print('Ask: does greedy fail? If yes, consider DP.')

Contagem de subproblemas distintos

# Sub-problem count examples:
# Problem          | Sub-problems  | Each costs | Total
# Fibonacci        | O(n)          | O(1)       | O(n)
# Coin change      | O(amount)     | O(coins)   | O(amount * coins)
# LCS (m,n chars) | O(m*n)        | O(1)       | O(m*n)
# Edit distance    | O(m*n)        | O(1)       | O(m*n)
# 0/1 Knapsack    | O(n*W)        | O(1)       | O(n*W)
# Matrix chain     | O(n^2)        | O(n)       | O(n^3)

# Rule: DP time = (# distinct sub-problems) * (time per sub-problem)
print('Time = subproblems * work-per-subproblem')

Roubo de casas: escolhas sobrepostas

def rob(nums):
    if not nums: return 0
    if len(nums) == 1: return nums[0]
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1],          # skip house i
                    dp[i-2] + nums[i]) # rob house i
    return dp[-1]

print(rob([1, 2, 3, 1]))   # 4: rob house 0 and 2 (1+3)
print(rob([2, 7, 9, 3, 1]))# 12: rob house 0, 2, 4 (2+9+1)
print(rob([2, 1, 1, 2]))   # 4: rob house 0 and 3

Verificação de consistência: força bruta versus DP

# Brute-force for house robber (exponential)
def rob_brute(nums, i=0):
    if i >= len(nums):
        return 0
    # Option 1: rob house i
    rob_it = nums[i] + rob_brute(nums, i + 2)
    # Option 2: skip house i
    skip_it = rob_brute(nums, i + 1)
    return max(rob_it, skip_it)

# Verify on small inputs:
test_cases = [[1,2,3,1], [2,7,9,3,1], [2,1,1,2]]
for tc in test_cases:
    bf = rob_brute(tc)
    dp = rob(tc)
    print(f'{tc}: brute={bf}, dp={dp}, match={bf==dp}')

Verificação rápida

Recapitulação da lição