Mochila ilimitada e troco de moedas II

Na mochila ilimitada, cada item pode ser escolhido qualquer número de vezes (ao contrário da mochila 0/1, em que cada item é usado no máximo uma vez). A definição do estado é a mesma — dp[c] = valor máximo possível com capacidade c —, mas a direção do percurso muda. Como os itens podem ser reutilizados, ao atualizar dp[c] queremos permitir que o item atual seja usado novamente; por isso, percorremos a capacidade da esquerda para a direita (para frente).

Na mochila 0/1, percorríamos a capacidade da direita para a esquerda para impedir a reutilização. Na mochila ilimitada, fazemos o oposto: percorremos da esquerda para a direita. Ao calcular dp[c], dp[c-w] já foi atualizado na passagem atual — o que significa que o item i possivelmente já foi incluído. É exatamente isso que queremos: o item i pode ser adicionado novamente a uma solução que já contém o item i.

A Troca de Moedas II pergunta: dadas as denominações das moedas e um valor, conte o número de maneiras distintas de obter esse valor (cada moeda pode ser usada um número ilimitado de vezes). Essa é uma variante da mochila ilimitada em que, em vez de maximizar o valor, contamos combinations. Defina dp[c] como o número de maneiras de obter o valor c. Caso base: dp[0] = 1 (há uma maneira de obter 0: não escolher nada).

Para cada moeda, percorra os valores da esquerda para a direita e acumule: dp[c] += dp[c - coin]. O caso base dp[0] = 1 inicia a contagem. Observe que o laço externo percorre as moedas e o laço interno percorre os valores — isso produz naturalmente contagens de combinations (não de permutations), pois cada denominação de moeda é considerada exatamente uma vez como passagem externa.

A ordem dos laços é fundamental. Se colocarmos o valor no laço externo e a moeda no laço interno, contaremos permutations (a ordem importa). Para amount=5 com as moedas [1,2], 1+2+2 e 2+1+2 serão contadas separadamente. Se colocarmos a moeda no laço externo, contaremos combinations (a ordem não importa): 1+2+2 e 2+1+2 serão a mesma. A Troca de Moedas II pede combinations, portanto a moeda fica no laço externo.

Outro problema clássico de mochila ilimitada: dada uma haste de comprimento n e os preços para cada comprimento de haste de 1 a n, encontre a maior receita cortando a haste da melhor forma. Cada peça de comprimento l pode ser vendida por price[l], e as peças podem ser reutilizadas (a haste pode ser cortada em várias peças do mesmo comprimento). Isso corresponde diretamente à mochila ilimitada, com W = n e os diferentes comprimentos de corte como itens.

A Troca de Moedas I (um problema diferente) pede o número mínimo de moedas necessário para obter um valor-alvo. Aqui, dp[c] = número mínimo de moedas para obter o valor c. Recorrência: dp[c] = min(dp[c], dp[c - coin] + 1). Inicialize todas as entradas com inf, exceto dp[0] = 0. Esse problema também é ilimitado (as moedas podem ser reutilizadas), portanto percorra os valores da esquerda para a direita. Retorne dp[amount] se for finito; caso contrário, -1.

As três variantes da mochila ilimitada usam operações diferentes sobre dp[c-coin]: Maximizar o valor: dp[c] = max(dp[c], dp[c-w] + v); inicializar com 0. Minimizar o custo: dp[c] = min(dp[c], dp[c-coin] + 1); inicializar com inf, dp[0]=0. Contar maneiras: dp[c] += dp[c-coin]; inicializar com 0, dp[0]=1. Reconhecer qual variante se aplica é metade do caminho para resolver problemas de entrevista.

Todas as variantes da mochila ilimitada executam em O(n × W) de tempo e O(W) de espaço, em que n é o número de tipos de itens e W é o valor-alvo. Em problemas de moedas, n é o número de denominações de moedas. Em entrevistas, informe a variante (máximo/mínimo/contagem), escreva a DP 1D e deixe claro se o laço externo percorre as moedas ou o valor — os avaliadores sabem que essa distinção testa uma compreensão profunda de DP.

Use estes sinais para identificar qual variante se aplica: reutilização ilimitada → ilimitada (percurso para frente); cada item exatamente uma vez → 0/1 (percurso para trás); o problema diz “qualquer número de vezes”, “suprimento infinito” ou “reutilização permitida” → ilimitada. Exemplos: troca de moedas, corte de haste, quebra de inteiro — todos são ilimitados. Soma de subconjuntos, partição, mochila 0/1 — 0/1. Errar essa identificação causa respostas incorretas difíceis de depurar.

Quebra de inteiro (LeetCode 343): divida um inteiro n em pelo menos 2 inteiros positivos para maximizar o produto entre eles. Essa é uma mochila ilimitada em que os “itens” são os inteiros de 2 a n-1. Defina dp[i] = produto máximo de inteiros cuja soma é i. Para cada item j de 2 a i, dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j])). Isso mostra como o padrão ilimitado se generaliza para além do contexto de moedas.

Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação apresentados nesta lição.

Nesta lição, você aprendeu: a mochila ilimitada percorre a capacidade da esquerda para a direita para permitir a reutilização dos itens, a Troca de Moedas II conta combinations colocando a moeda no laço externo e as três variantes — maximizar, minimizar e contar — diferem apenas na operação da DP e na inicialização. Em seguida, usaremos a mochila 0/1 para resolver o problema de Partição em Subconjuntos de Soma Igual.