Dato 2 array di numeri non negativi, trovare la somma minima di prodotti

Question

Date due matrici A e B, ciascuno contenente n numeri non negativi, rimuovere a>0 elementi dalla fine di A e b>0 elementi da fine B. Valutare il costo di un'operazione come X*Y dove X è la somma degli elementi a rimossi da A e Y la somma degli elementi b rimossi da B. Continua a farlo finché entrambi gli array non sono vuoti. L'obiettivo è ridurre al minimo il costo totale.

Utilizzo della programmazione dinamica e il fatto che una strategia ottimale richiede sempre esattamente un elemento da A o B È possibile trovare una soluzione O (n^3). Ora sono curioso di sapere se c'è una soluzione ancora più veloce a questo problema?

EDIT: Rubare un esempio @recursive nei commenti:

A = [1,9,1] e B = [1, 9, 1]. Possibile fare con un costo di 20. (1) * (1 + 9) + (9 + 1) * (1)

Answer 1

Ecco O(n^2). Lascia che sia CostA(i, j) il costo minimo per eliminare A[1..i], B[1..j] in modo che la prima rimozione richieda solo un elemento da B. Sia il CostB(i, j) il costo minimo dell'eliminazione di A[1..i], B[1..j] in modo che la prima rimozione richieda un solo elemento da A. Abbiamo recidive mutuamente ricorsive

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)) 

casi di base

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

La risposta è min(CostA(n, n), CostB(n, n)).