Prerrequisito: ¿Cómo resolver un problema de programación dinámica?
Hay muchos tipos de problemas que piden contar el número de enteros ‘ x ‘ entre dos enteros, digamos ‘ a ‘ y ‘ b ‘ tales que x satisface una propiedad específica que se puede relacionar con sus dígitos.
Entonces, si decimos que G(x) indica el número de tales enteros entre 1 y x (inclusive), entonces el número de tales enteros entre a y b puede ser dado por G(b) – G(a-1) . Aquí es cuando Digit DP (Programación Dinámica) entra en acción. Todos los problemas de conteo de enteros que satisfacen la propiedad anterior se pueden resolver mediante el método de DP de dígitos.
Concepto clave:
- Sea el número dado x tiene n dígitos. La idea principal de digit DP es representar primero los dígitos como una array de dígitos t[]. Digamos que tenemos t n t n-1 t n-2 … t 2 t 1 como la representación decimal donde t i (0 < i <= n) indica el i-ésimo dígito desde la derecha. El dígito más a la izquierda t n es el dígito más significativo.
- Ahora, después de representar el número dado de esta manera, generamos los números menores que el número dado y simultáneamente calculamos usando DP, si el número satisface la propiedad dada. Comenzamos generando números enteros con un número de dígitos = 1 y luego hasta un número de dígitos = n. Los enteros que tienen menos dígitos que n se pueden analizar estableciendo los dígitos más a la izquierda en cero.
Problema de ejemplo:
dados dos enteros a y b . Tu tarea es imprimir la suma de
todos los dígitos que aparecen en los enteros entre a y b.
Por ejemplo, si a = 5 y b = 11, entonces la respuesta es 38 (5 + 6 + 7 + 8 + 9 + 1 + 0 + 1 + 1)
Restricciones : 1 <= a < b <= 10^18
Ahora vemos que si hemos calculado la respuesta para el estado que tiene n-1 dígitos, es decir, t n-1 t n-2 … t 2 t 1 y necesitamos calcular la respuesta para el estado que tiene n dígitos t n t n-1 t n- 2 … t 2 t 1. Entonces, claramente, podemos usar el resultado del estado anterior en lugar de volver a calcularlo. Por lo tanto, sigue la propiedad de superposición.
Pensemos en un estado para este DP
Nuestro estado DP será dp(idx, tight, sum)
1) idx
- Habla sobre el valor del índice desde la derecha en el entero dado
2) apretado
- Esto le dirá si el rango de dígitos actual está restringido o no. Si el rango del dígito actual
no está restringido, abarcará de 0 a 9 (inclusive), de lo contrario, abarcará
de 0 a digit[idx] (inclusive).
Ejemplo : considere que nuestro número entero límite es 3245 y necesitamos calcular G(3245)
índice: 4 3 2 1
dígitos: 3 2 4 5
Rango sin restricciones:
ahora suponga que el número entero generado hasta ahora es: 3 1 * * (* es un lugar vacío, donde se insertarán los dígitos para formar el número entero).
index : 4 3 2 1 digits : 3 2 4 5 generated integer: 3 1 _ _
aquí, vemos que el índice 2 tiene un rango sin restricciones. Ahora el índice 2 puede tener dígitos del 0 al 9 (inclusive).
Para rango no restringido apretado = 0
Rango restringido:
Ahora suponga que el número entero generado hasta ahora es: 3 2 * * (‘*’ es un lugar vacío, donde se insertarán los dígitos para formar el número entero).
index : 4 3 2 1 digits : 3 2 4 5 generated integer: 3 2 _ _
aquí, vemos que el índice 2 tiene un rango restringido. Ahora el índice 2 solo puede tener dígitos del rango 0 al 4 (inclusive)
Para rango restringido apretado = 1
3) suma
- Este parámetro almacenará la suma de dígitos en el entero generado de msd a idx.
- El valor máximo para la suma de este parámetro puede ser 9*18 = 162, considerando 18 dígitos en el número entero
Relación de estado:
La idea básica para la relación de estado es muy simple. Formulamos el dp en forma de arriba hacia abajo.
Digamos que estamos en el msd con índice idx. Entonces, inicialmente, la suma será 0.
Por lo tanto, completaremos el dígito en el índice con los dígitos en su rango. Digamos que su rango es de 0 a k (k<=9, dependiendo del valor ajustado) y obtenga la respuesta del siguiente estado que tenga índice = idx-1 y suma = suma anterior + dígito elegido.
int ans = 0; for (int i=0; i<=k; i++) { ans += state(idx-1, newTight, sum+i) } state(idx,tight,sum) = ans;
¿Cómo calcular el valor newTight?
El nuevo valor ajustado de un estado depende de su estado anterior. Si el valor ajustado del estado anterior es 1 y el dígito en idx elegido es digit[idx](es decir, el dígito en idx en el número entero límite), entonces solo nuestro nuevo ajustado será 1, ya que solo entonces indica que el número se formó hasta ahora es el prefijo del entero limitante.
// digitTaken is the digit chosen // digit[idx] is the digit in the limiting // integer at index idx from right // previouTight is the tight value form previous // state newTight = previousTight & (digitTake == digit[idx])
A continuación se muestra la implementación del enfoque anterior.
CPP
// Given two integers a and b. The task is to print // sum of all the digits appearing in the // integers between a and b #include "bits/stdc++.h" using namespace std; // Memoization for the state results long long dp[20][180][2]; // Stores the digits in x in a vector digit long long getDigits(long long x, vector <int> &digit) { while (x) { digit.push_back(x%10); x /= 10; } } // Return sum of digits from 1 to integer in // digit vector long long digitSum(int idx, int sum, int tight, vector <int> &digit) { // base case if (idx == -1) return sum; // checking if already calculated this state if (dp[idx][sum][tight] != -1 and tight != 1) return dp[idx][sum][tight]; long long ret = 0; // calculating range value int k = (tight)? digit[idx] : 9; for (int i = 0; i <= k ; i++) { // calculating newTight value for next state int newTight = (digit[idx] == i)? tight : 0; // fetching answer from next state ret += digitSum(idx-1, sum+i, newTight, digit); } if (!tight) dp[idx][sum][tight] = ret; return ret; } // Returns sum of digits in numbers from a to b. int rangeDigitSum(int a, int b) { // initializing dp with -1 memset(dp, -1, sizeof(dp)); // storing digits of a-1 in digit vector vector<int> digitA; getDigits(a-1, digitA); // Finding sum of digits from 1 to "a-1" which is passed // as digitA. long long ans1 = digitSum(digitA.size()-1, 0, 1, digitA); // Storing digits of b in digit vector vector<int> digitB; getDigits(b, digitB); // Finding sum of digits from 1 to "b" which is passed // as digitB. long long ans2 = digitSum(digitB.size()-1, 0, 1, digitB); return (ans2 - ans1); } // driver function to call above function int main() { long long a = 123, b = 1024; cout << "digit sum for given range : " << rangeDigitSum(a, b) << endl; return 0; }
Java
// Java program for above approach import java.util.ArrayList; import java.util.Arrays; // Given two integers a and b. The task is to print // sum of all the digits appearing in the // integers between a and b public class GFG { // Memoization for the state results static long dp[][][] = new long[20][180][2]; // Stores the digits in x in a vector digit static void getDigits(long x, ArrayList<Integer> digit) { while (x != 0) { digit.add((int)(x % 10)); x /= 10; } } // Return sum of digits from 1 to integer in // digit vector static long digitSum(int idx, int sum, int tight, ArrayList<Integer> digit) { // base case if (idx == -1) return sum; // checking if already calculated this state if (dp[idx][sum][tight] != -1 && tight != 1) return dp[idx][sum][tight]; long ret = 0; // calculating range value int k = (tight != 0) ? digit.get(idx) : 9; for (int i = 0; i <= k; i++) { // calculating newTight value for next state int newTight = (digit.get(idx) == i) ? tight : 0; // fetching answer from next state ret += digitSum(idx - 1, sum + i, newTight, digit); } if (tight != 0) dp[idx][sum][tight] = ret; return ret; } // Returns sum of digits in numbers from a to b. static int rangeDigitSum(int a, int b) { // initializing dp with -1 for (int i = 0; i < 20; i++) for (int j = 0; j < 180; j++) for (int k = 0; k < 2; k++) dp[i][j][k] = -1; // storing digits of a-1 in digit vector ArrayList<Integer> digitA = new ArrayList<Integer>(); getDigits(a - 1, digitA); // Finding sum of digits from 1 to "a-1" which is // passed as digitA. long ans1 = digitSum(digitA.size() - 1, 0, 1, digitA); // Storing digits of b in digit vector ArrayList<Integer> digitB = new ArrayList<Integer>(); getDigits(b, digitB); // Finding sum of digits from 1 to "b" which is // passed as digitB. long ans2 = digitSum(digitB.size() - 1, 0, 1, digitB); return (int)(ans2 - ans1); } // driver function to call above function public static void main(String[] args) { int a = 123, b = 1024; System.out.println("digit sum for given range : " + rangeDigitSum(a, b)); } } // This code is contributed by Lovely Jain
Python3
# Given two integers a and b. The task is to # print sum of all the digits appearing in the # integers between a and b # Memoization for the state results dp = [[[-1 for i in range(2)] for j in range(180)]for k in range(20)] # Stores the digits in x in a list digit def getDigits(x, digit): while x: digit.append(x % 10) x //= 10 # Return sum of digits from 1 to integer in digit list def digitSum(index, sumof, tight, digit): # Base case if index == -1: return sumof # Checking if already calculated this state if dp[index][sumof][tight] != -1 and tight != 1: return dp[index][sumof][tight] ret = 0 # Calculating range value k = digit[index] if tight else 9 for i in range(0, k+1): # Calculating newTight value for nextstate newTight = tight if digit[index] == i else 0 # Fetching answer from next state ret += digitSum(index-1, sumof+i, newTight, digit) if not tight: dp[index][sumof][tight] = ret return ret # Returns sum of digits in numbers from a to b def rangeDigitSum(a, b): digitA = [] # Storing digits of a-1 in digitA getDigits(a-1, digitA) # Finding sum of digits from 1 to "a-1" which is passed as digitA ans1 = digitSum(len(digitA)-1, 0, 1, digitA) digitB = [] # Storing digits of b in digitB getDigits(b, digitB) # Finding sum of digits from 1 to "b" which is passed as digitB ans2 = digitSum(len(digitB)-1, 0, 1, digitB) return ans2-ans1 a, b = 123, 1024 print("digit sum for given range: ", rangeDigitSum(a, b)) # This code is contributed by rupasriachanta421
Producción:
digit sum for given range : 12613
Complejidad del tiempo :
hay un total de estados idx*sum*tight y estamos realizando de 0 a 9 iteraciones para visitar cada estado. Por lo tanto, la complejidad del tiempo será O(10*idx*sum*tight) . Aquí, observamos que tight = 2 e idx pueden tener un máximo de 18 para un entero sin signo de 64 bits y, además, la suma será un máximo de 9*18 ~ 200. Por lo tanto, en general tenemos 10*18*200*2 ~ 10^5 iteraciones que se puede ejecutar fácilmente en 0,01 segundos .
El problema anterior también se puede resolver usando recursividad simple sin ninguna memorización. La solución recursiva para el problema anterior se puede encontrar aquí . Pronto agregaremos más problemas en digit dp en nuestras publicaciones futuras.
Este artículo es aportado porNitish Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA