Problema 322: Troco Mínimo (Coin Change)

O objetivo deste problema é determinar a quantidade mínima de moedas necessárias para compor um valor específico. Trata-se de uma variação do problema da mochila completa, onde o foco é minimizar a quantidade de itens utilizados.

• Estado DP: minCoins[v] representa o número mínimo de moedas necessárias para formar o valor v.
• Transição: minCoins[v] = min(minCoins[v], minCoins[v - coin] + 1). A cada moeda avaliada, verificamos se o uso dela reduz a quantidade total de moedas para o valor atual.
• Inicialização: minCoins[0] = 0, pois zero moedas são necessárias para formar o valor zero. Para os demais índices, inicializamos com um valor que represente o infinito (como targetAmount + 1) para permitir que a operação de mínimo funcione corretamente sem causar overflow.
• Ordem de Iteração: Como o objetivo é encontrar a quantidade mínima de itens e não o número de combinações ou permutações, a ordem de iteração (capacidade externa e itens internos, ou vice-versa) não altera o resultado final.

class Solution {
public:
    int coinChange(vector<int>& denominations, int targetAmount) {
        vector<int> minCoins(targetAmount + 1, targetAmount + 1);
        minCoins[0] = 0;
        
        for (int currentAmount = 1; currentAmount <= targetAmount; ++currentAmount) {
            for (int coin : denominations) {
                if (currentAmount >= coin) {
                    minCoins[currentAmount] = min(minCoins[currentAmount], minCoins[currentAmount - coin] + 1);
                }
            }
        }
        
        return (minCoins[targetAmount] > targetAmount) ? -1 : minCoins[targetAmount];
    }
};

Problema 279: Quadrados Perfeitos (Perfect Squares)

Neste cenário, o número n atua como a capacidade máxima da mochila, e os quadrados pefreitos são os itens disponíveis. O valor e o peso de cada item são equivalentes ao próprio quadrado perfeito.

• Estado DP: leastSquares[k] armazena a menor quantidade de quadrados perfeitos cuja soma resulta em k.
• Transição: leastSquares[k] = min(leastSquares[k], leastSquares[k - sq] + 1), onde sq é um quadrado perfeito válido.
• Inicialização: leastSquares[0] = 0 e os demais valores são definidos como limit + 1 para atuar como um limite superior seguro.
• Otimização de Estrutura: Em vez de pré-calcular e armazenar um array com todos os quadrados perfeitos até n, podemos calcular o quadrado dinamicamente durante o loop, o que economiza memória e simplifica a lógica.

class Solution {
public:
    int numSquares(int limit) {
        vector<int> leastSquares(limit + 1, limit + 1);
        leastSquares[0] = 0;
        
        for (int val = 1; val <= limit; ++val) {
            for (int base = 1; base * base <= val; ++base) {
                int perfectSquare = base * base;
                leastSquares[val] = min(leastSquares[val], leastSquares[val - perfectSquare] + 1);
            }
        }
        
        return leastSquares[limit];
    }
};

Problema 139: Segmentação de Palavras (Word Break)

Aqui, a "capacidade" da mochila é o comprimento da string alvo, e os "itens" são as palavras disponíveis no dicionário. O problema exige uma resposta booleana, verificando se a string pode ser totalmente segmentada.

• Estado DP: isSegmentable[i] indica se a subcadeia de caracteres da string original até o índice i pode ser formada pela concatenação de palavras do dicionário.
• Transição: Se a subcadeia s[j...i-1] existe no dicionário e isSegmentable[j] é verdadeiro, então isSegmentable[i] também se torna verdadeiro. Isso garante que todas as partes anteriores já foram validadas.
• Inicialização: isSegmentable[0] = true, pois uma string vazia é trivialmente válida. Os demais índices começam como false.
• Ordem de Iteração: Diferente dos problemas anteriores, a ordem das palavras importa para formar a string exata (caracterizando uma permutação). Portanto, é obrigatório iterar primeiro sobre a capacidade (comprimento da string) e depois sobre os itens (pontos de corte da substring).

class Solution {
public:
    bool wordBreak(string text, vector<string>& vocabulary) {
        unordered_set<string> validWords(vocabulary.begin(), vocabulary.end());
        int textLen = text.length();
        vector<bool> isSegmentable(textLen + 1, false);
        isSegmentable[0] = true;
        
        for (int endIdx = 1; endIdx <= textLen; ++endIdx) {
            for (int startIdx = 0; startIdx < endIdx; ++startIdx) {
                if (isSegmentable[startIdx]) {
                    string segment = text.substr(startIdx, endIdx - startIdx);
                    if (validWords.count(segment)) {
                        isSegmentable[endIdx] = true;
                        break;
                    }
                }
            }
        }
        
        return isSegmentable[textLen];
    }
};