Troco

Este é, com certeza, um dos problemas de DP mais clássicos, e é de fundamental importância, para um programador competitivo, que ele o entenda e domine, para ser capaz de resolver todas as sua variações.

A ideia é muito simples: sabendo todos os possíveis valores de moedas de um país, é possível formar um determinado valor usando as moedas. Suponha, por exemplo, que um país tem moedas de 2, 5 e 7 centavos. É possível dar um troco de 19 centavos? Sim, basta usarmos 2 moedas de 5, uma de 7 e uma de 2 centavos.

Para implementarmos esta DP, primeiro precisamos pensar em qual o seu estado. De maneira muito intuitiva, vamos fazer algo bem semelhante ao Knapsack e usar o valor que queremos formar como estado da DP. Deste modo, \(DP(x)\) retornará true se for possível conseguir exatamente o valor \(x\) com as moedas que tenho disponível, e false caso contrário.

Pensemos, agora, como em toda DP, nos casos base. Se \(x=0\), então é fácil conseguir este valor: basta não usarmos moeda alguma. Além disso, se \(x<0\), então não conseguimos este valor, pois não temos moedas negativas.

Agora, vamos tentar montar a recursão. Se tenho um valor \(x>0\), vou tentar formá-lo usando cada uma das moedas disponíveis. Seja \(c_i\) o valor da \(i\)-ésima moeda. Note que, para qualquer \(i\), eu consigo usar a moeda \(i\) para formar o valor \(x\) se, e somente se, eu conseguir formar, com as moedas, o valor \(x-c_i\), pois usaríamos a combinação de moedas que forma este valor, mais a moeda \(i\), para conseguirmos o valor \(x\)

Agora, você já deve ter entendido o que deve fazer. Basta percorrer todos os possíveis valores de \(i\) (todas as moedas), testando se consegue formar o valor \(x-c_i\), usando recursão para isso. Se você conseguir, com qualquer uma das moedas, então você consegue formar o valor \(x\), e \(DP(x)\) deve retornar true.

Agora, basta tabelar os resultados e temos a DP pronta! O código a seguir é de uma função que recebe como parâmetros o valor inteiro x, que desejamos formar, e um vetor de inteiros c, onde c[i] representa o valor da \(i\)-ésima moeda. Lembre-se de inicializar todos os valores da DP como -1 (não calculado) e, para cada estado, ela retornará 1, se for true, ou 0, caso seja false.

            int dp[MAX];
            int solve(int x, vector<int> &c){
                if(x==0) return 1;
                if(x<0) return 0;
                if(dp[x]>=0) return dp[x];
                for(int i=0;i<c.size();i++)
                    if(solve(x-c[i])) return dp[x-c[i]]=1;

                return dp[x]=0;
            }

No código acima, a função retorna true assim que encontramos uma maneira de formar o valor \(x\). Se testarmos todas as moedas e nenhuma funcionar, ela retorna false. Note que o valor de \(x\) deve ser menor que MAX.

Sobre a complexidade do código, temos \(x\) possíveis estados. Se tivermos \(n\) moedas, cada estado tem complexidade linear no valor de \(n\), logo, a complexidade final da DP é \(O(x \cdot n)\).