与えられる2つのアレイは、2つのアレイ<code>A</code>と<code>B</code>、各含有<code>n</code>非負の数を考える製品

Question

の最小和を見つけるBの端部からAの端からa>0要素とb>0要素を削除しますそのような操作のコストを、XがAとYから削除されたa要素の合計であるb要素の合計がBから削除されたものであると評価します。両方の配列が空になるまで、これを続けます。目標は総コストを最小限に抑えることです。

動的計画法と、最適戦略が常にAまたはBから1つの要素を取るという事実を利用すると、O（n^3）の解が見つかります。今私は、この問題のさらに高速な解決策があるかどうかを知りたいのですか？

EDIT：コメントで@recursiveから例を盗む：

A = [1,9,1]とB = [1、9,1]。 20のコストで行うことが可能（1）* （1 + 9）+（9 + 1）*（1）

Answer 1

はここO(n^2)です。 CostA(i, j)をA[1..i], B[1..j]を除去するための最小コストとすると、最初の除去がBから1つの要素のみを取るようになります。 CostB(i, j)をA[1..i], B[1..j]を除去するための最小コストとすると、最初の除去ではAから1つの要素しか取られません。私たちは、答えはmin(CostA(n, n), CostB(n, n))であるベースケースと相互に再帰的な再発

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

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

を持っています。