Programação Dinâmica com dígitos [Pt 1]

Programação dinâmica (PD) em dígitos é uma subclasse dos problemas de PD. Existem muitas variações, nessa parte falamos da forma: Dado um intervalo A e B, quantos números x, A <= x <= B, tem uma propriedade específica.

No nosso caso, vamos usar o problema: quantos números menores que X existem tal que a soma dos dígitos é exatamente 20. Existem várias formas de resolver, e irei mostrar uma.


Observações iniciais

Se o intervalo A a B é pequeno o suficiente -- digamos 1 a 1000 --, podemos iterar por todos esses números em tempo O(1000-1) e checar manualmente número por número, mas isso não é desejado para B-A grande.

Um truque simples é que o resultado entre A e B é igual ao resultado de 0 a B menos o resultado de 0 a A-1.

Mas antes, imagine que não existe restrição de número, apenas no número de dígitos. Por exemplo, queremos saber quantos números existem de 00000 a 99999 -- qualquer número de 5 dígitos é válido. Nesse caso, utilizamos de programação dinâmica e dizemos que dp[n][sum] é o estado que diz quantos dígitos faltam adicionar (n) à resposta e a soma ideial que obtivemos até o momento (sum). A recorrência é da forma:

dp[n][sum] = dp[n-1][sum-0] + dp[n-1][sum-1] + ... + dp[n-1][sum-9]

Por exemplo, para 5 dígitos com soma 20 e 19, temos:

dp[5][20] = dp[4][20] + dp[4][19] + dp[4][18] + ... + dp[4][11]
dp[5][19] = dp[4][19] + dp[4][18] + ... + dp[4][10]

Queremos computar justamente dp[n][20]. Os casos base são dp[0][0] = 1, e dp[0][x] = 0 se x != 0, pois é o caso em que não falta adicionar nenhum dígito (a soma só pode ser 0).

Recursão

O algoritmo abaixo calcula a PD. Observe que na recursão memorizamos as respostas, para que elas não sejam computadas várias vezes -- técnica chamada de memoization. Por exemplo: dp[4][19] é utilizada para computar dp[5][20] e dp[5][19], e na segunda vez o valor salvo antes é usado.

int dp[N][20];            // N numero maximo de digitos
memset(dp, -1, sizeof(dp)) // Preenche a matriz toda com -1

int calc(int digit, int sum) {
    if (sum < 0) return 0; // soma abaixo do valor
    if (digit == 0) return (soma == 0); // retorna 1 se soma for 0, e 0 caso contrario

    int& ans = dp[digit][sum];         // Cria uma referencia pro valor
    if (ans != -1) return ans;         // Se diferente de -1, ja foi computado

    ans = 0;
    for (int d = 0; d <= 9; d++) {
        ans += calc(digit-1, sum - d);
    }
    return ans;
}

PS: Colocar & em "int& ans = var" é criar uma referência na memória para var. Quando ans é modificada, var também é, ou seja, elas tem sempre o mesmo valor.

Calculando a resposta

A recursão anterior calcula quantos números existem com n dígitos, mas o problema é quantos números inferiores a X existem -- Imagine que x é 03234 (limitante), e temos que preencher 5 dígitos (_ _ _ _ _).

Para o primeiro dígito, estamos presos no limitante e não há opção, ele só pode ser 0, pois outro valor ultrapassaria o limite (0 _ _ _ _).

Para o segundo dígito, há 4 opções -- 0, 1, 2 ou 3. Observe que, se colocamos 0, 1 ou 2, não há restrição nos outros dígitos (perdemos o limitante), portanto qualquer número de três dígitos restantes é válido, e a PD anterior pode ser usada. Se colocarmos 3 continuamos com a restrição:

Repetindo esse processo, o código final fica algo como abaixo.

int compute(char *numero, int n) {
    int ans = 0, acum = 20;
    // acum eh a soma acumulada que desejamos pros digitos restantes

    for (int i = 0; i < n; i++) {
        int limit = numero[i] - '0';
        // O loop repete para todos os digitos inferiores ao limitante
        for (int d = 0; d < limit; d++) {
            ans += calc(n-i-1, acum - d);
            // Faltam colocar n-i-1 digitos e o acumulado decrementa
        }
        acum -= numero[i] - '0';
    }
    return ans;
}

Problema sugerido:
Spoj GONE: G-one numbers [link]

Continuar para parte 2 [link].
Códigos no github [link].