2024.04.06

Este artigo explora os fundamentos da programação dinâmica, abordando quatro problemas clássicos que demonstram diferentes aplicações dessa técnica poderosa:

• Mochila Completa
• Troco de Moedas II
• Soma de Combinações IV
• Divisão de Palavras

A metodologia para resolver problemas de programação dinâmica envolve cinco passos essenciais:

1. Definir o array dp e o significado de seus índices
2. Estabelecer a fórmula de recorrência
3. Inicializar o array dp
4. Determinar a ordem de iteração
5. Exemplificar a derivação do array dp

Mochila Completa

**Problema:**Um pesquisador precisa selecionar materiais para uma conferência internacional, mas tem limitações de espaço na bagagem. Cada material tem um peso específico e um valor associado. A mochila suporta um peso máximo N. O objetivo é maximizar o valor total dos materiais selecionados, considerando que cada item pode ser escolhido infinitas vezes.

Entrada:

• Primeira linha: dois inteiros N e V, representando o número de tipos de materiais e o espaço disponível
• Próximas N linhas: cada linha contém dois inteiros wi e vi, representando o peso e o valor do material i

**Saída:**Um inteiro representando o valor máximo possível.

Exemplo de Entrada:

4 5
1 2
2 4
3 4
4 5

Exemplo de Saída:

10

**Solução:**Aplicando os cinco passos da programação dinâmica:

1. Definição do array dp:dp[i] representa o valor máximo que pode ser armazenado com capacidade i.
2. Fórmula de recorrência:dp[j] = max(dp[j], dp[j-pesos[i]] + valores[i])
3. Inicialização:dp[0] = 0 (capacidade zero resulta em valor zero)
4. **Ordem de iteração:**Iterar sobre os itens e depois sobre as capacidades.
5. **Exemplo de derivação:**Para cada capacidade, calcular o valor máximo considerando a inclusão ou não do item atual.

Implementação em Java:

import java.util.Scanner;

class MochilaCompleta {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int quantidadeItens = scanner.nextInt();
        int capacidade = scanner.nextInt();
        
        int[] pesos = new int[quantidadeItens];
        int[] valores = new int[quantidadeItens];
        
        for (int i = 0; i < quantidadeItens; i++) {
            pesos[i] = scanner.nextInt();
            valores[i] = scanner.nextInt();
        }
        
        int[] dp = new int[capacidade + 1];
        dp[0] = 0;
        
        for (int i = 0; i < quantidadeItens; i++) {
            for (int j = pesos[i]; j <= capacidade; j++) {
                dp[j] = Math.max(dp[j], dp[j - pesos[i]] + valores[i]);
            }
        }
        
        System.out.println(dp[capacidade]);
    }
}

Complexidade Temporal: O(n * V) Complexidade Espacial: O(V)

Troco de Moedas II

**Problema:**Dado um array de inteiros coins representando diferentes denominações de moedas e um inteiro amount, calcule o número de maneiras de formar o amount usando essas moedas. Cada moeda pode ser usada infinitas vezes.

Entrada:

amount = 5, coins = [1, 2, 5]

Saída:

4

**Explicação:**Existem quatro maneiras de formar o amount:

1. 5
2. 2 + 2 + 1
3. 2 + 1 + 1 + 1
4. 1 + 1 + 1 + 1 + 1

Solução:

1. Definição do array dp:dp[j] represanta o número de maneiras de formar o valor j.
2. Fórmula de recorrência:dp[j] += dp[j - coins[i]]
3. Inicialização:dp[0] = 1 (existe uma maneira de formar o valor zero: não usar nenhuma moeda)
4. **Ordem de iteração:**Iterar sobre as moedas e depois sobre os valores.
5. **Exemplo de derivação:**Para cada moeda, atualizar o array dp para todos os valores que podem ser formados incluindo essa moeda.

Implementação em Java:

class SolucaoTroco {
    public int calcularTroco(int valorTotal, int[] moedas) {
        int[] dp = new int[valorTotal + 1];
        dp[0] = 1;
        
        for (int moeda : moedas) {
            for (int j = moeda; j <= valorTotal; j++) {
                dp[j] += dp[j - moeda];
            }
        }
        
        return dp[valorTotal];
    }
}

Complexidade Temporal: O(n * amount) Complexidade Espacial: O(amount)

Soma de Combinações IV

**Problema:**Dado um array de inteiros distintos nums e um alvo target, retorne o número de combinações de elementos de nums que somam target. Sequências diferentes são consideradas combinações diferentes.

Entrada:

nums = [1, 2, 3], target = 4

Saída:

7

**Explicação:**As combinações possíveis são:

1. (1, 1, 1, 1)
2. (1, 1, 2)
3. (1, 2, 1)
4. (1, 3)
5. (2, 1, 1)
6. (2, 2)
7. (3, 1)

Solução:

1. Definição do array dp:dp[i] representa o número de combinações que somam o valor i.
2. Fórmula de recorrência:dp[i] += dp[i - nums[j]]
3. Inicialização:dp[0] = 1 (uma combinação vazia soma zero)
4. **Ordem de iteração:**Para problemas de permutação, iterar sobre os valores primeiro e depois sobre os números.
5. **Exemplo de derivação:**Para cada valor de 1 a target, calcular o número de combinações considerando cada número disponível.

Implementação em Java:

class SolucaoCombinacoes {
    public int encontrarCombinacoes(int[] numeros, int alvo) {
        int[] dp = new int[alvo + 1];
        dp[0] = 1;
        
        for (int i = 1; i <= alvo; i++) {
            for (int numero : numeros) {
                if (i >= numero) {
                    dp[i] += dp[i - numero];
                }
            }
        }
        
        return dp[alvo];
    }
}

Complexidade Temporal: O(target * n) Complexidade Espacial: O(target)

Divisão de Palavras

**Problema:**Dada uma string s e uma lista de palavras wordDict, determine se s pode ser segmentada em uma ou mais palavras que existem em wordDict. As palavras podem ser reutilizadas.

Entrada:

s = "leetcode", wordDict = ["leet", "code"]

Saída:

true

**Explicação:**A string "leetcode" pode ser dividida em "leet" e "code", ambas presentes no dicionário.

Solução:

1. Definição do array dp:dp[i] é true se a substring s[0:i] pode ser dividida em palavras do dicionário.
2. **Fórmula de recorrência:**Se dp[j] é true e a substring s[j:i] está no dicionário, então dp[i] é true.
3. Inicialização:dp[0] = true (uma string vazia pode ser dividida)
4. **Ordem de iteração:**Iterar sobre os comprimentos de string e sobre os possíveis pontos de divisão.
5. **Exemplo de derivação:**Para cada posição na string, verificar se pode ser formada combinando uma substring válida com uma string anteriormente validada.

Implementação em Java:

import java.util.HashSet;
import java.util.List;
import java.util.Set;

class SolucaoDivisaoPalavras {
    public boolean podeDividirPalavra(String texto, List<String> dicionario) {
        Set<String> conjuntoPalavras = new HashSet<>(dicionario);
        boolean[] valido = new boolean[texto.length() + 1];
        valido[0] = true;
        
        for (int i = 1; i <= texto.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (!valido[i] && valido[j] && conjuntoPalavras.contains(texto.substring(j, i))) {
                    valido[i] = true;
                }
            }
        }
        
        return valido[texto.length()];
    }
}

Complexidade Temporal: O(n³) Complexidade Espacial: O(n)

Para problemas de mochila múltipla, consulte recursos especializados. Para uma visão geral abrangente dos problemas de mochila, recomenda-se explorar materiais de referência detalhados sobre o assunto.