समस्या
मूल (अंग्रेज़ी) दिखाएँमैट्रिक्स 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
उदाहरण
उदाहरण 1
इनपुट:
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 से सस्ती है।
उदाहरण 2
इनपुट:
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।
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।