Please enable JavaScript.

Coggle requires JavaScript to display documents.

inicio - Coggle Diagram

- - - - Programação Dinâmica resolve subproblemas que são sobrepostos
      - Dividir para Conquistar resolve subproblemas que são independente
  - - - Em vez de começar de cima (n) e descer, começamos de baixo (0 e 1). Calculamos F(2) usando F(0) e F(1), depois F(3) usando F(1) e F(2), e assim por diante até chegar em F(n)
    - - F(n)=max(cn+F(n−2),F(n−1))
    - - ara encontrar o mínimo de moedas para o valor n, verificamos o mínimo necessário para n - valor_da_moeda para cada tipo de moeda disponível e somamos 1.
  - - - Problema da Mochila (Knapsack Problem)
        
        Objetivo: Maximizar o Valor Total sem estourar a Capacidade (W).
        
        Entrada: Lista de itens (cada um com peso w e valor v) e capacidade W.
        
        Lógica (Recorrência): Para cada item, decida entre:
        
        Não levar: Valor mantém o mesmo da linha anterior (mesma capacidade).
        
        Levar: Valor do item atual + melhor valor possível com o espaço restante.
        
        Fórmula: F(i,j)=max{F(i−1,j),vi+F(i−1,j−wi)}
        
        Resultado: O valor na célula final da tabela (último item, capacidade total).
        
        Funções de Memória (Memoization)
        
        O que é: Híbrido entre Recursão (Top-Down) e Tabela DP (Bottom-Up).
        
        Problema da DP clássica: Preenche a tabela inteira, mesmo células inúteis.
        
        Solução Memoization:
        
        Começa recursivo do fim.
        
        Antes de calcular, checa a tabela.
        
        Se vazio → calcula e salva.
        
        Se existe → usa o valor salvo.
        
        Vantagem: Calcula apenas os estados necessários.