को देखते हुए गैर नकारात्मक संख्या 2 सरणियों,, उत्पादों

Question

दो सरणियों A और B, प्रत्येक युक्त n गैर नकारात्मक संख्या को देखते हुए की न्यूनतम राशि को खोजने के बी के अंत से एक के अंत से a>0 तत्वों और b>0 तत्वों को दूर X*Y रूप में इस तरह के ऑपरेशन की लागत जहां XA और YB से हटा b तत्वों का योग से हटा a तत्वों का योग है का मूल्यांकन करें। यह तब तक जारी रखें जब तक कि दोनों सरणी खाली न हों। लक्ष्य कुल लागत को कम करना है।

गतिशील प्रोग्रामिंग का उपयोग करना और तथ्य यह है कि एक इष्टतम रणनीति हमेशा A या B से बिल्कुल एक तत्व लेती है, मुझे ओ (एन^3) समाधान मिल सकता है। अब मुझे यह जानकर उत्सुकता है कि इस समस्या का एक और तेज समाधान है या नहीं?

संपादित करें: टिप्पणी में @recursive से एक उदाहरण चोरी:

एक = [1,9,1] और बी = [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 से केवल एक तत्व लेता है। CostB(i, j)A[1..i], B[1..j] को इस तरह से समाप्त करने की न्यूनतम लागत हो कि पहले हटाने को A से केवल एक तत्व लेता है। हम पारस्परिक रूप से पुनरावर्ती पुनरावृत्ति

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. 

जवाब min(CostA(n, n), CostB(n, n)) है के साथ की है।