Algorithmus Dynamische Programmierung

Question

Sie erhalten ein Array bestehend aus Zahlen (Größe des Arrays 10^5) und Sie müssen das Array in K Partition teilen (k < = 500), so dass die Summe des minimalen Elements jeder Partition maximal ist

sagen Array enthält a1, a2, a3 ....... ein jetzt f (x) = min (a1, a2..ax) + min (a (x + 1), a (x + 2) ... ay) + .......... a (z + 1), .... a (n)

nun f (x) sollte

wo Partition maximal sein muss zusammenhängend sein.
Erforderliche Komplexität. (N * k)

Ich reparierte einfach das maximale Element eines nach der anderen und versuchte, zu sehen, wenn es in K Trennwand geteilt werden kann oder nicht, wenn ja, ich f berechnet (x)

Answer 1

Lassen dp[i] = f(x) wenn die Anzahl der Partitionen ist i wobei f (x) ist wie durch OP definiert starten lässt es jetzt zu lösen - Basis Case-

dp[n]=sum(array elements); 
//ie when number of partitions is n we return sum of elements as each element is in different partition 

jetzt

dp[i-1] = dp[i] - min of partition collapsed in this step 

So, jetzt müssen wir einfach die Partition finden, die bei jedem Schritt reduziert werden muss. Dies kann durch Brute-Force erfolgen, indem zwei benachbarte Partitionen gleichzeitig genommen werden und ein Tab beibehalten wird, dessen Kollaps am ungünstigsten ist (kann in O (n) durchgeführt werden).

Also ist die gesamte Zeitkomplexität O (n * n-k) und die Raumkomplexität ist O (n). Nun, das ist die Grenze für Fähigkeiten, die jeder, der helfen kann, zu verbessern, ist willkommen.