समस्या
मैट्रिक्स i का आकार dimensions[i] × dimensions[i+1] है। एक p×q मैट्रिक्स को q×r मैट्रिक्स से गुणा करने में p·q·r स्केलर गुणा लगते हैं। श्रृंखला में कहाँ-कहाँ कोष्ठक (parentheses) लगाएँ ताकि पूरी श्रृंखला को गुणा करने की कुल लागत न्यूनतम हो।
min_multiplications(dimensions) को इम्प्लीमेंट करें।
इनपुट
dimensions: n + 1 आकार, जो n मैट्रिक्स का वर्णन करते हैं।
आउटपुट
न्यूनतम कुल लागत लौटाएँ।
सीमाएँ
2 ≤ dimensions की लंबाई ≤ 200; 1 ≤ प्रत्येक आकार ≤ 500
उदाहरण
इनपुट:
dimensions = [10, 30, 5, 60]
अपेक्षित आउटपुट:
expected = 4500इनपुट:
std::vector<long long> dimensions = {10, 30, 5, 60};
अपेक्षित आउटपुट:
long long expected = 4500;इनपुट:
long[] dimensions = new long[] {10, 30, 5, 60};
अपेक्षित आउटपुट:
long expected = 4500;व्याख्या
(A×B)×C की लागत 10·30·5 + 10·5·60 = 4500 है, जो A×(B×C) = 27000 से सस्ती है।
इनपुट:
dimensions = [5, 10]
अपेक्षित आउटपुट:
expected = 0इनपुट:
std::vector<long long> dimensions = {5, 10};
अपेक्षित आउटपुट:
long long expected = 0;इनपुट:
long[] dimensions = new long[] {5, 10};
अपेक्षित आउटपुट:
long expected = 0;व्याख्या
एक अकेला मैट्रिक्स गुणा की आवश्यकता नहीं होती: 0।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Multiplication का order total cost बदल देता है, भले final matrix shape वही रहे.
संकेत 2
हर interval के लिए हर possible split point try करें और छोटे interval results reuse करें.
संकेत 3
Dimensions array को ध्यान से use करें: हर subproblem matrices की endpoints पर निर्भर करता है, सिर्फ matrix count पर नहीं.
अपेक्षित जटिलता
समय O(n^3), अतिरिक्त स्थान O(n^2)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।