¿Cómo se puede dividir una secuencia de enteros ‘n’ en particiones ‘k’ de modo que la suma total de la suma al cuadrado de todas las particiones ‘k’ sea mínima?

Planteamiento del problema:
¿Cómo se puede dividir una secuencia de N enteros en K subconjuntos contiguos de modo que la suma total de la suma al cuadrado de todas las K particiones sea mínima?

Solución:

Defina un estado DP [math] dp (i, \ j) [/ math] que denota la suma total mínima de la suma al cuadrado de las particiones [math] j [/ math] mientras recorre los primeros enteros [math] i [/ math] secuencia dada

Ahora, si desea calcular la respuesta para este estado, es bastante obvio que ya habría calculado las respuestas para todas [matemáticas] dp (x, \ y) [/ matemáticas] de modo que [matemáticas] x <i [/ math] y [math] y <j [/ math].

Dicho esto, las siguientes ecuaciones deberían ser ciertas.

[matemáticas] dp (i, \ 1) \ = \ acumulativo [i] \ \ forall \ i \ \ in \ [1, N] [/ matemáticas]
[matemáticas] dp (i, \ j) \ = \ min (dp (s, \ j \ – \ 1) \ + \ cumulative [i] \ – \ cumulative [s]) \ \ forall \ s \ \ in \ [1, \ s \ – \ 1] [/ matemáticas]

Aquí, [math] acumulativo [i] [/ math] denota la suma del prefijo de los primeros enteros [math] i [/ math] de la secuencia dada. Entonces, básicamente mientras calcula [math] dp (i, \ j) [/ math], pasa a considerar todas las longitudes posibles de la partición [math] j ^ {th} [/ math] que termina en index [math] yo [/ matemáticas].

Ahora, [math] dp (N, \ K) [/ math] debería darte la respuesta requerida. La complejidad general de la solución será [matemática] O (N * N * K) [/ matemática]

Si le gustó mi respuesta, también podría leer mi publicación de blog [1] sobre Programación dinámica.

Notas al pie

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