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