2 angegebenen Arrays von nicht-negativen Zahlen, finden die minimale Summe von Produkten

Question

Gegeben seien zwei Arrays A und B mit jeweils n nicht-negative Zahlen, entfernen a>0 Elemente aus dem Ende von A und b>0 Elemente aus dem Ende des B. Berechnen Sie die Kosten für einen solchen Vorgang wie X ist die Summe der a Elemente aus A und Y die Summe der b Elemente aus B entfernt entfernt. Machen Sie dies solange, bis beide Arrays leer sind. Ziel ist es, die Gesamtkosten zu minimieren.

Mit dynamischer Programmierung und der Tatsache, dass eine optimale Strategie immer genau ein Element von A oder B benötigt, kann ich eine O (n^3) -Lösung finden. Jetzt bin ich neugierig zu wissen, ob es eine noch schnellere Lösung für dieses Problem gibt?

EDIT: ein Beispiel aus den Kommentaren in @recursive Stealing:

A = [1,9,1] und B = [1, 9, 1]. Mögliche mit Kosten von 20. (1) * (1 + 9) + (9 + 1) * (1)

Answer 1

Hier ist O(n^2) zu tun. Lassen Sie CostA(i, j) die minimalen Kosten für die Beseitigung A[1..i], B[1..j] in einer solchen Weise, dass die erste Entfernung nur ein Element aus B. Lassen Sie CostB(i, j) die minimalen Kosten für die Beseitigung A[1..i], B[1..j] in einer solchen Weise sein, dass die erste Entfernung nur ein Element aus A. Wir haben für beide Seiten rekursive Rezidive

CostA(i, j) = A[i] * B[j] + min(CostA(i - 1, j), 
           CostA(i - 1, j - 1), 
           CostB(i - 1, j - 1)) 
CostB(i, j) = A[i] * B[j] + min(CostB(i, j - 1), 
           CostA(i - 1, j - 1), 
           CostB(i - 1, j - 1)) 

mit Basis Fällen

CostA(0, 0) = 0 
CostA(>0, 0) = infinity 
CostA(0, >0) = infinity 
CostB(0, 0) = 0 
CostB(>0, 0) = infinity 
CostB(0, >0) = infinity. 

Die Antwort ist min(CostA(n, n), CostB(n, n)).