Cómo calcular el producto máximo de una cadena entera usando k multiplicaciones

Suponiendo que tenemos computadoras increíbles para manejar multiplicaciones de grandes números al instante, me gustaría proponer la solución que utiliza la programación dinámica.

Pasemos a definir nuestro estado DP como [math] F (i, j) [/ math] que denotará el producto máximo logrado al considerar los primeros caracteres [math] i [/ math] de cadena y usar exactamente [math] j [/ math] operadores de multiplicación. Por lo tanto, nuestra respuesta requerida estará representada por el estado [matemáticas] F (N, K) [/ matemáticas].

Según las definiciones anteriores, nuestra recurrencia se puede definir de la siguiente manera. Aquí [math] P [i, j] [/ math] denota el valor numérico de la subcadena [math] S [i, j] [/ math] para la cadena dada [math] S [/ math]

• [matemáticas] F (0, 0) [/ matemáticas] [matemáticas] = [/ matemáticas] [matemáticas] 1 [/ matemáticas]

• Cadena vacía que tiene operadores de multiplicación [matemática] 0 [/ matemática].

• Será imposible tener una cadena de longitud [matemática] i [/ matemática] insertada con más de operadores de multiplicación [matemática] i [/ matemática]. Por lo tanto, el estado está marcado como indefinido.

• Usar estados anteriores para calcular la respuesta óptima para el estado actual.

La complejidad del enfoque anterior se puede expresar en [matemáticas] O (K * N ^ {2}) [/ matemáticas]. Si le gusta resolver problemas basados ​​en programación dinámica, puede leer la siguiente publicación de blog escrita.

Programación dinámica – Parte 1 por Prateek Gupta en TechParoksha

Supongamos que usamos los primeros dígitos X para formar el primer número, ahora lo multiplicaremos con el número máximo alcanzable con los dígitos restantes y los operadores K-1.

Si K es cero, tomamos toda la cadena como un número.
Entonces, un posible estado DP es (posición, k_izquierda).

Deberíamos usar divide y vencerás este problema.

¿Puedes responder las siguientes preguntas?

1. Solo un número, es decir, S = 1 yk = 0. ¿Cuál es la solución?

2. Solo dos números, es decir, si S = 12 yk = 0. La solución de esto es muy simple, ¿no?

2. ¿Qué pasa con S = 12 y k = 1 caso? En ese caso, simplemente pondrá ‘*’ en el medio como este 1 * 2 y sabrá la respuesta.

3. ¿Cómo generalizamos esto? Como ya sabemos, ‘*’ debe insertarse en todas partes hasta que se agote, es decir, alcancemos el límite k.

S = 12345 yk = 2. Pongamos ‘*’ en el medio como este 123 * 45. Luego resolvemos para la izquierda, que es 123. Ahora tenemos k = 1 e ingresamos como 123. Pongamos * de nuevo en el medio. 12 * 3 y nos queda k = 0. Entonces volvemos al caso ‘1’ como se explicó anteriormente y ya lo ha resuelto. Podemos hacer lo mismo para el caso correcto, pero para el caso correcto que es 45, k es cero y, como ya se explicó, k es cero ya está resuelto como en el caso ‘1’.

El código sigue:

producto def (entrada, inicio, fin, k):
resultado = -1
si inicio <= fin:
si memorizar [inicio] [fin]! = 0:
volver memorizar [inicio] [fin]
si no k:
return int (input [inicio: fin + 1])
para i en rango (inicio, fin):
result = max (result, max ((product (input, start, i, k-1) * int (input [i + 1: end + 1]), (int (input [start: i + 1]) * * product (entrada, i + 1, final, k-1)))))
memorizar [inicio] [fin] = resultado
resultado devuelto

datos = str (4609110)
memoize = [[0 para x en rango (len (datos) +1)] para x en rango (len (datos) +1)]
print (producto (datos, 0, len (datos) -1, 3))