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

Na parte 1, vimos como resolver o problema de quantos números existem entre 0 e B com uma propriedade, e dissemos que para computar de A a B basta fazer de 0 a B menos de 0 a A-1. O problema é que nem sempre dá certo. Por exemplo, se quisessemos o número entre A e B com maior soma de dígitos, essa estratégia não funcionaria!

Vamos agora ver como resolver de outra forma então, mais genérica, mas que pode ser mais lenta.

Como exemplo, vamos usar o problema: quantos números menores que X e maiores que Y existem tal que a soma dos dígitos é exatamente 20.



Modificando a recursão

Vamos voltar ao exemplo da parte 1: quantos números menores que 03234 existem cuja soma dos digitos é exatamente 20.

O primeiro dígito só pode ser 0, enquanto o segundo pode ser 0, 1, 2 e 3. Se colocamos 0 ou 1 ou 2, perdemos a restrição de limitante (pois poderíamos preencher o resto dos números com 999), mas se colocamos 3, ainda temos a restrição (o resto deve ser menor que 234).

Na parte 1, definimos a PD que diz quantos números com n dígitos existem, e criamos uma função compute que chama a PD. Para remover a função compute, podemos adicionar na DP uma informação: estamos presos ao limitante ou não -- um bit (0 ou 1).

Dizemos que ehMenor é 0 se estamos preso a restrição, e que ehMenor passa a ser 1 quando perdemos a restrição (quando colocamos 2 no lugar de 3, por exemplo). Observe que ehMenor só passa de 0 para 1, mas nunca de 1 para 0.

int dp[N][20][2];
char numero[5] = "03234";
memset(dp, -1, sizeof(dp)); // Seta a matriz -1

int calc(int digit, int sum, int ehMenor) {
    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][ehMenor];         // Cria uma referencia pro valor
    if (ans != -1) return ans;         // Se diferente de -1, ja foi computado
   
    ans = 0;
    int limit;

    // Se estamos fora do limitante, podemos colocar qualquer digito ate 9
    if (ehMenor == 1) limit = 9;
    // Se nao, limite com base no valor do limitante superior  
    else limit = numero[digit] - '0';

    // Avaliamos todos os digitos de 0 ate o limite
    for (int d = 0; d <= limit; d++) {
        int novoEhMenor;
        
        // Caso em que ehMenor passa de 0 para 1
        if (ehMenor == 0 && d < limit) novoEhMenor = 1;
        else novoEhMenor = ehMenor;

        ans += calc(digit-1, sum - d, novoEhMenor);
    }

    return ans;
}

int main() {
    calc(5, 20, 0); // 5 digitos, soma 20, ehMenor comeca igual a 0 
}

Essa PD já trata então todos os números abaixo do limitante superior!

Adicionando o limitante inferior

Digamos que temos o mesmo problema, mas queremos os números entre 01222 e 03234. O primeiro dígito é 0, e o segundo agora só pode ser 1, 2 ou 3.

Se colocamos 1, os demais devem ser maior que 222, se colocamos 2 eles podem ser qualquer coisa (de 000 até 999), e se colocamos 3 eles devem ser menor que 234). Portanto, temos um limitante inferior. Alterar a solução anterior não é complicado.

int dp[N][20][2][2];
char superior[5] = "03234";
char inferior[5] = "01222";
memset(dp, -1, sizeof(dp)); // Seta a matriz -1

int calc(int digit, int sum, int ehMenor, int ehMaior) {
    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][ehMenor][ehMaior];
    if (ans != -1) return ans;         // Se diferente de -1, ja foi computado
   
    ans = 0;
    int inf, sup;

    // Se estamos abaixo do teto, podemos colocar qualquer digito ate 9
    if (ehMenor == 1) sup = 9;
    // Se nao, limite superior com base no valor do teto
    else sup = superior[digit] - '0';

    // Se estamos acima do piso, podemos colocar qualquer digito acima de 0
    if (ehMaior == 1) inf = 0;
    // Se nao, limite inferior com base no valor do piso
    else inf = inferior[digit] - '0';

    // Avaliamos numeros entre inf e sup
    for (int d = inf; d <= sup; d++) {
        int novoEhMenor, novoEhMaior

        if (ehMenor == 0 && d < sup) novoEhMenor = 1;
        else novoEhMenor = ehMenor;
        if (ehMaior == 0 && d > inf) novoEhMaior = 1;
        else novoEhMaior = ehMaior

        ans += calc(digit-1, sum - d, novoEhMenor, novoEhMaior);
    } 
   
    return ans;
}

int main() {
    calc(5, 20, 0, 0); // 5 digitos, soma 20, ehMenor/ehMaior comeca igual a 0 
}

O código está grande assim para ficar mais claro, mas ele pode ser encurtado! A função abaixo faz a mesma coisa.

int calc(int digit, int sum, int ehMenor, int ehMaior) {
    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][ehMenor][ehMaior];
    if (ans != -1) return ans;         // Se diferente de -1, ja foi computado
   
    ans = 0;
    int sup = (ehMenor == 1) ? 9 : superior[digit] - '0';
    int inf = (ehMaior == 1) ? 0 : inferior[digit] - '0';

    for (int d = inf; d <= sup; d++) {
        // e se dissermos que 4 eh um digito proibido?
        // basta fazer if (d == 4) continue; e ele sera ignorado
        ans += calc(digit-1, sum - d, ehMenor | (d < sup), ehMaior | (d > inf));
    } 
   
    return ans;
}

OBS: Uma desvantagem desse jeito é que a PD depende dos limites! Do jeito anterior da parte 1, podemos precomputar a PD e em seguida calcular para diferentes limites mais rapidamente.

Problema sugerido:
CS Academy: Banned digits [link]

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