DP de Baixo para Cima com Tabulação
Converta soluções de cima para baixo em tabelas DP iterativas e reduza o espaço de O(n) para O(1) quando apenas as últimas entradas forem necessárias.
DP de Baixo para Cima com Tabulação é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
DP de baixo para cima: a abordagem de tabulação
DP de baixo para cima (tabulação) preenche uma tabela de respostas dos subproblemas, começando pelos menores subproblemas e avançando até chegar à resposta. Em vez de descer por recursão e armazenar os resultados em cache na volta, você calcula iterativamente a partir da base. A tabela normalmente é um vetor 1D ou 2D, em que cada célula é calculada a partir de células preenchidas anteriormente. Isso elimina completamente a recursão — sem pilha de chamadas, sem limite de recursão e com melhor localidade de cache.
# Converting top-down to bottom-up:
# Top-down: start at fib(n), recurse to smaller, cache
# Bottom-up: start at fib(0), fill table to fib(n)
# Key question for bottom-up:
# 'In what order do I fill the table so that when I compute dp[i],
# all values dp[i] depends on are already filled?'
# For Fibonacci: dp[i] needs dp[i-1] and dp[i-2]
# Fill order: i = 2, 3, 4, ..., n (left to right)
print('Bottom-up: fill small sub-problems first, build to answer')Fibonacci de baixo para cima
O Fibonacci de baixo para cima preenche dp[0..n] da esquerda para a direita. dp[i] = dp[i-1] + dp[i-2] para i >= 2. Os casos-base são dp[0] = 0 e dp[1] = 1, armazenados diretamente no vetor. O tempo é O(n) e o espaço é O(n) para a tabela completa. Quando perceber que dp[i] depende apenas dos dois últimos valores, você poderá reduzir o espaço para O(1) com duas variáveis — essa é a etapa de otimização de espaço.
def fib_bottom_up(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0 # base case
dp[1] = 1 # base case
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print([fib_bottom_up(i) for i in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
# Space-optimised to O(1):
def fib_optimised(n):
if n <= 1: return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
print(fib_optimised(50)) # 12586269025Troca de moedas de baixo para cima
Para a troca de moedas, a tabela de baixo para cima é dp[0..amount], em que dp[i] = número mínimo de moedas para formar o valor amount i. Inicialize dp[0] = 0 (zero moedas para valor zero) e dp[1..amount] = infinito. Para cada valor i de 1 até o alvo, tente cada moeda: se i >= coin, então dp[i] = min(dp[i], 1 + dp[i - coin]). A resposta é dp[amount], ou -1 se ainda for infinito.
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # base case: 0 coins for amount 0
for i in range(1, amount + 1):
for coin in coins:
if i >= coin: # can use this coin
dp[i] = min(dp[i], 1 + dp[i - coin])
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change([1, 5, 6, 9], 11)) # 2: (5+6)
print(coin_change([2], 3)) # -1: impossible
print(coin_change([1, 2, 5], 11)) # 3: 5+5+1
print(coin_change([186, 419, 83, 408], 6249)) # 20Ordem de preenchimento: a ideia essencial
A ordem de preenchimento é o ponto central da DP de baixo para cima. Para qualquer estado dp[i], todos os estados de que ele depende devem ser calculados primeiro. Em uma DP 1D na qual dp[i] depende de dp[i-1] e dp[i-2], preencha da esquerda para a direita. Em uma DP 2D na qual dp[i][j] depende de dp[i-1][j] e dp[i][j-1], preencha linha por linha (de cima para baixo e da esquerda para a direita). Sempre desenhe as setas de dependência antes de escrever o código para confirmar a ordem de preenchimento.
# Fill order examples:
# 1D: dp[i] = f(dp[i-1], dp[i-2])
# Arrows point LEFT: fill LEFT TO RIGHT
# i: 0 -> 1 -> 2 -> ... -> n
# 2D: dp[i][j] = f(dp[i-1][j], dp[i][j-1])
# Arrows point LEFT and UP: fill TOP-LEFT TO BOTTOM-RIGHT
# Fill row 0 first, then row 1, etc.
# 2D reversed: dp[i][j] = f(dp[i+1][j], dp[i][j+1])
# Arrows point RIGHT and DOWN: fill BOTTOM-RIGHT TO TOP-LEFT
# Used in interval DP and some string problems
print('Draw dependencies first, then determine fill order')LCS de baixo para cima: tabela 2D
A tabela de baixo para cima da maior subsequência comum tem dimensões (m+1) × (n+1), em que dp[i][j] representa a LCS de s1[:i] e s2[:j]. Casos-base: dp[0][j] = dp[i][0] = 0 (uma cadeia vazia tem LCS 0 com qualquer outra). Preencha linha por linha: se s1[i-1] == s2[j-1], dp[i][j] = 1 + dp[i-1][j-1]; caso contrário, dp[i][j] = max(dp[i-1][j], dp[i][j-1]). A resposta é dp[m][n].
def lcs_bottom_up(s1, s2):
m, n = len(s1), len(s2)
# (m+1) x (n+1) table, initialised to 0
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]: # characters match
dp[i][j] = 1 + dp[i-1][j-1]
else: # skip one character
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
print(lcs_bottom_up('abcde', 'ace')) # 3
print(lcs_bottom_up('ABCBDAB', 'BDCAB')) # 4: 'BCAB' or 'BDAB'Otimização de espaço: vetor rolante
Muitas tabelas 2D de DP podem ser reduzidas a 1D (ou a 2 linhas) observando que dp[i][j] depende apenas da linha atual e da linha anterior. Mantenha dois vetores: prev e curr, ou atualize um único vetor na ordem correta. Para LCS, dp[i][j] depende de dp[i-1][j], dp[i][j-1] e dp[i-1][j-1] — manter apenas a linha anterior é suficiente.
def lcs_space_optimised(s1, s2):
m, n = len(s1), len(s2)
# Keep only one row (previous row state)
prev = [0] * (n + 1)
for i in range(1, m + 1):
curr = [0] * (n + 1)
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
curr[j] = 1 + prev[j-1] # dp[i-1][j-1]
else:
curr[j] = max(prev[j], curr[j-1]) # dp[i-1][j] and dp[i][j-1]
prev = curr
return prev[n]
print(lcs_space_optimised('abcde', 'ace')) # 3
# Space: O(n) instead of O(mn)Roubo de casas de baixo para cima
O roubo de casas de baixo para cima preenche dp[0..n-1], em que dp[i] = lucro máximo ao roubar as casas de 0 até i. dp[0] = nums[0], dp[1] = max(nums[0], nums[1]) e, para i >= 2: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Como dp[i] depende apenas dos dois últimos valores, o espaço é imediatamente otimizado para O(1) com duas variáveis — um padrão comum em DP 1D com dependências de duas etapas.
def rob_bottom_up(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
# Full table version: O(n) space
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], dp[i-2] + nums[i])
return dp[-1]
def rob_optimised(nums):
# O(1) space: only need last two values
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2, prev1 = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
return prev1
print(rob_optimised([2, 7, 9, 3, 1])) # 12Soma mínima de caminho em uma grade
Soma mínima de caminho (LeetCode #64): encontre um caminho do canto superior esquerdo ao canto inferior direito que minimize a soma dos valores (só é possível mover-se para a direita ou para baixo). DP 2D: dp[i][j] = soma mínima para alcançar a célula (i,j). dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Preencha da esquerda para a direita e de cima para baixo. Caso-base: dp[0][0] = grid[0][0]; a primeira linha é preenchida apenas para a direita, e a primeira coluna, apenas para baixo.
def min_path_sum(grid):
rows, cols = len(grid), len(grid[0])
dp = [[0] * cols for _ in range(rows)]
dp[0][0] = grid[0][0]
# Fill first row (can only come from left)
for c in range(1, cols):
dp[0][c] = dp[0][c-1] + grid[0][c]
# Fill first column (can only come from above)
for r in range(1, rows):
dp[r][0] = dp[r-1][0] + grid[r][0]
# Fill rest of the table
for r in range(1, rows):
for c in range(1, cols):
dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])
return dp[rows-1][cols-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid)) # 7: 1+3+1+1+1Modificando a tabela de DP diretamente
Quando espaço extra é proibido, às vezes você pode modificar a própria grade de entrada e usá-la como tabela de DP. Para a soma mínima de caminho, sobrescreva grid[i][j] com o custo mínimo para alcançar essa célula. Isso usa O(1) de espaço extra, mas destrói a entrada — sempre mencione essa troca ao entrevistador e confirme se ela é aceitável. Se a entrada precisar ser preservada, use a abordagem do vetor rolante.
def min_path_sum_inplace(grid):
rows, cols = len(grid), len(grid[0])
# Modify grid in-place (O(1) extra space, destroys input)
for r in range(rows):
for c in range(cols):
if r == 0 and c == 0:
continue # starting cell
elif r == 0:
grid[r][c] += grid[r][c-1] # first row
elif c == 0:
grid[r][c] += grid[r-1][c] # first column
else:
grid[r][c] += min(grid[r-1][c], grid[r][c-1])
return grid[rows-1][cols-1]
import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid))) # 7Comparando as abordagens de cima para baixo e de baixo para cima na troca de moedas
Ambas as abordagens resolvem a troca de moedas de forma ideal, mas diferem na prática. A abordagem de cima para baixo é mais simples de escrever e calcula apenas os subproblemas que são realmente alcançáveis. A abordagem de baixo para cima calcula todos os valores de 0 até o alvo, inclusive aqueles que não podem ser alcançados com as moedas fornecidas (que permanecem com valor infinito). Para problemas esparsos (com poucos estados alcançáveis), a abordagem de cima para baixo é mais eficiente; para problemas densos, a abordagem de baixo para cima tem menor sobrecarga.
import functools
# Top-down: only computes reachable amounts
def coin_change_top(coins, amount):
@functools.lru_cache(maxsize=None)
def dp(rem):
if rem == 0: return 0
if rem < 0: return float('inf')
return 1 + min(dp(rem - c) for c in coins)
r = dp(amount)
return r if r != float('inf') else -1
# Bottom-up: computes all amounts 0 to target
def coin_change_bottom(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for c in coins:
if i >= c: dp[i] = min(dp[i], 1 + dp[i-c])
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change_top([1,5,6,9], 11)) # 2
print(coin_change_bottom([1,5,6,9], 11)) # 2Caminhos Únicos: DP 2D Clássica
Caminhos Únicos (LeetCode #62) conta o número de caminhos do canto superior esquerdo ao canto inferior direito de uma grade m×n, movendo-se apenas para a direita ou para baixo. A recorrência é direta: dp[i][j] = dp[i-1][j] + dp[i][j-1] — caminhos vindos de cima mais caminhos vindos da esquerda. Casos-base: a primeira linha inteira e a primeira coluna inteira têm exatamente 1 caminho cada (há apenas uma direção possível para avançar). Essa DP 2D preenche a tabela em tempo O(mn) e pode ser reduzida para O(n) de espaço com uma linha deslizante.
def unique_paths(m, n):
# dp[i][j] = number of paths to reach cell (i,j)
dp = [[1] * n for _ in range(m)]
# Base: first row and first column are all 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
print(unique_paths(3, 7)) # 28
print(unique_paths(3, 2)) # 3
# O(n) space rolling row:
def unique_paths_opt(m, n):
row = [1] * n
for _ in range(1, m):
for j in range(1, n):
row[j] += row[j-1]
return row[n-1]
print(unique_paths_opt(3, 7)) # 28Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu: DP de baixo para cima com tabulação e como determinar a ordem de preenchimento a partir das setas de dependência, otimização de espaço usando matrizes deslizantes (de O(mn) para O(n)) e o acompanhamento de duas variáveis (de O(n) para O(1)), além de implementações de baixo para cima de Fibonacci, troca de moedas, LCS, ladrão de casas e soma mínima de caminhos. A seguir, resolveremos os problemas de troca de moedas e escadas de custo mínimo de ponta a ponta.
Aprenda Python com um tutor de IA — grátis
Escreva e execute código real no seu navegador, obtenha ajuda instantânea de um tutor de IA 24/7 e continue de onde parou na web ou no app.
- Cursos
- 30
- Aulas
- 120
Perguntas Frequentes
A aula “DP de Baixo para Cima com Tabulação” é grátis?
Sim — o texto completo de “DP de Baixo para Cima com Tabulação” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “DP de Baixo para Cima com Tabulação”?
Converta soluções de cima para baixo em tabelas DP iterativas e reduza o espaço de O(n) para O(1) quando apenas as últimas entradas forem necessárias. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “DP de Baixo para Cima com Tabulação”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de DSA Interview Prep?
Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Reconhecendo DP: Subproblemas Sobrepostos
- DP de Cima para Baixo com Memoização
- DP de Baixo para Cima com Tabulação
- Troca de Moedas e Escada de Custo Mínimo