--- id: 6999b92ca334e9cf237dc92d title: Revisão de Programação Dinâmica challengeType: 31 dashedName: review-dynamic-programming-js --- # --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.

function climbStairsMemo(n, memo = {}) {
  // If already calculated, return cached value
  if (memo[n] !== undefined) {
    return memo[n];
  }

  // Base cases: 1 way for 1 step, 2 ways for 2 steps
  if (n <= 2) {
    return n;
  }

  // Calculate once and store in memo for future use
  memo[n] =
    climbStairsMemo(n - 1, memo) +
    climbStairsMemo(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.

function climbStairsTabulation(n) {
  if (n <= 2) {
    return n;
  }

  // Create an array to store solutions from 0 to n
  const dp = new Array(n + 1).fill(0);

  // Base cases
  dp[1] = 1; // 1 way to reach step 1
  dp[2] = 2; // 2 ways to reach step 2

  // Build up the solution iteratively
  for (let i = 3; i <= n; i++) {
    // 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.

# --assignment-- Revise os tópicos e conceitos de Programação Dinâmica.