Reduzierung der zeitlichen Komplexität in der maximalen Minimalsumme 2-Partitionierung eines Arrays

Lassen Sie array[N] ein Array von N nicht-negativen Werten. Wir versuchen, das Array rekursiv in zwei (2) Sub-Arrays zu partitionieren, so dass wir die maximale "Minimum-Summe" jedes Sub-Arrays erreichen können. Die Lösung wird durch die folgende Rekursion beschrieben:

Wir wollen opt[0][N-1] berechnen.

Lassen Sie c[x][y] die sum{array[i]} von x bis y (einschließlich) angeben. Ich habe es geschafft, die Rekursion im folgenden C ++ - Code-Snippet mit dynamischer Programmierung abzuwickeln:

Diese Technik analysiert alle Unterfelder, beginnend mit der Größe 1 und bis zur Größe N . Die endgültige Lösung wird somit in opt[0][N-1] gespeichert.

Beispiel: Wenn N=6 , wird die Matrix wie folgt iteriert: (0,0) (1,1) (2,2) (3,3) (4,4) (5,5) (0,1) (1,2) (2,3) (3,4) (4,5) (0,2) (1,3) (2,4) (3,5) (0,3) (1,4) (2,5) (0,4) (1,5) (0,5) . Die endgültige Antwort wird in opt[0][5] sein.

Ich habe getestet und verifiziert, dass die obige Technik funktioniert, um die Rekursion aufzuheben. Ich versuche die Komplexität weiter zu reduzieren, da dies in O (n ^ 3) laufen wird, wenn ich richtig liege. Konnte das erreicht werden?

edit: Ich merke auch die physikalische Bedeutung der Rekursion, wie sie in den Kommentaren gefragt wurde. Lassen Sie N für N Städte auf einer geraden Linie stehen. Wir sind ein Vermieter, der diese Städte kontrolliert; Am Ende eines Jahres zahlt jede Stadt i einen Vorrat an array[i] -Münzen, solange sie unter unserer Kontrolle steht.

Unsere Städte werden von einer überlegenen Macht angegriffen und eine Niederlage ist unvermeidlich. Zu Beginn jedes Jahres errichten wir eine Mauer zwischen zwei benachbarten Städten i , i+1 , x <= i <= y . Während jedes Jahres greifen die feindlichen Truppen entweder von Westen her an und erobern somit alle Städte in [x,i] , oder sie greifen aus dem Osten an und erobern somit alle Städte in [i+1,y] . Die verbleibenden Städte werden uns Ende des Jahres ihren Unterhalt zahlen. Die feindlichen Kräfte zerstören die Mauer am Ende des Jahres, ziehen sich zurück und starten im nächsten Jahr einen neuen Angriff. Das Spiel endet, wenn nur noch eine Stadt steht.

Die feindlichen Kräfte werden immer von der optimalen Position angreifen, um unser maximales Einkommen im Laufe der Zeit zu reduzieren. Unsere Strategie ist, die optimale Position der Wand zu wählen, um unser Gesamteinkommen am Ende des Spiels zu maximieren.