Interview Questions/Coding/Compute Pipeline Bracket Plan

Compute Pipeline Bracket Plan

Preview mode. Log in to edit, run, submit, and save progress.

Hard

Compute Pipeline Bracket Plan

A compute service multiplies a chain of matrices. Matrix Ai has dimensions dimensions[i - 1] by dimensions[i]. The order of multiplication can change the total computation cost, but the matrix order itself cannot be rearranged. Return one parenthesization that achieves the minimum multiplication cost. Matrix names must be written as A1, A2, and so on. If multiple optimal parenthesizations exist, return the one produced by the platform's left-to-right tie rule. Input Format: You are given an integer array dimensions. Output Format: Return an optimal parenthesization string.

Examples

Example 1

Input:

dimensions = [40, 20, 30, 10, 30]

Output:

((A1(A2A3))A4)

Explanation: For dimensions [40, 20, 30, 10, 30], the minimum scalar multiplication cost is 26000. The bracket plan ((A1(A2A3))A4) achieves that cost.

Approach hint

Classic interval DP stores the best split.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

solution.cpp