Revisão de Programação Dinâmica
---
id: 67f39e2119042d2f2ca926ff
title: Revisão de Programação Dinâmica
challengeType: 31
dashedName: review-dynamic-programming
---
# --description--
Introdução à Programação Dinâmica
- Definição: Programação dinâmica é uma técnica algorítmica que resolve problemas complexos dividindo-os em subproblemas mais simples e armazenando os resultados para evitar cálculos redundantes.
- Subproblemas Sobrepostos: Os mesmos problemas menores aparecem várias vezes ao resolver o problema maior. Em vez de recalcular esses subproblemas repetidamente, armazenamos suas soluções.
- Subestrutura Ótima: A solução ótima para o problema contém soluções ótimas para seus subproblemas. Isso significa que podemos construir a melhor solução combinando as melhores soluções para partes menores.
Soluções de Programação Dinâmica
- Memoização (Abordagem de Cima para Baixo): A memoização armazena os resultados de chamadas de função custosas e retorna o resultado em cache quando as mesmas entradas ocorrem novamente.
def climb_stairs_memo(n, memo={}):
"""Dynamic programming with memoization"""
# Check if we've already calculated this value
if n in memo:
return memo[n] # Return cached result - O(1) lookup!
# Base cases
if n <= 2:
return n
# Calculate once and store in memo for future use
memo[n] = climb_stairs_memo(n-1, memo) + climb_stairs_memo(n-2, memo)
return memo[n]- Tabulação (Abordagem Bottom-Up): A tabulação constrói a solução de baixo para cima, preenchendo uma tabela com soluções para subproblemas.
def climb_stairs_tabulation(n):
"""Dynamic programming with tabulation"""
if n <= 2:
return n
# Create array to store results for all steps from 0 to n
dp = [0] * (n + 1)
dp[1] = 1 # 1 way to reach step 1
dp[2] = 2 # 2 ways to reach step 2
# Build up the solution iteratively
for i in range(3, n + 1):
# Ways to reach step i = ways to reach (i-1) + ways to reach (i-2)
dp[i] = dp[i-1] + dp[i-2]
return dp[n]Aplicações do Mundo Real Usando Programação Dinâmica
- Otimização de Rotas: sistemas de GPS usam algoritmos de programação dinâmica para encontrar os caminhos mais curtos entre os locais.
- Processamento de Texto: Verificadores ortográficos e recursos de autocompletar frequentemente dependem de programação dinâmica para calcular distâncias de edição entre palavras.
- Modelagem Financeira: Estratégias de investimento e otimização de portfólio frequentemente empregam técnicas de programação dinâmica.
- Alocação de Recursos: O problema da mochila e suas variantes aparecem em agendamento, orçamento e gerenciamento de recursos.
Quando Usar Programação Dinâmica
Você deve considerar usar programação dinâmica nos seguintes cenários:- O problema pode ser dividido em subproblemas sobrepostos.
- O problema apresenta subestrutura ótima.
- Uma solução recursiva ingênua envolveria cálculos repetidos.
- Você precisa otimizar para complexidade de tempo ao custo da complexidade de espaço.