No. (AB)C costs 10·30·5 + 10·5·60 = 4,500. A(BC) costs 30·5·60 + 10·30·60 = 27,000. The intermediate result’s shape changes the work.

best(i,j) is the minimum multiplication cost for matrices i through j, inclusive. Matrix i has shape dims[i] × dims[i+1]. Assume compatible matrices and positive integer dimensions.

from functools import cache

def chain_cost(dims):
    if len(dims) < 2:
        return 0
    @cache
    def best(i, j):
        if i == j:
            return 0
        return min(best(i, k) + best(k + 1, j)
                   + dims[i] * dims[k + 1] * dims[j + 1]
                   for k in range(i, j))
    return best(0, len(dims) - 2)

assert chain_cost([10, 30, 5, 60]) == 4500
assert chain_cost([10, 20]) == 0

Every parenthesization has a final multiplication splitting the sequence at some k. For that split, the best left and right results are compatible because their outer dimensions depend only on the boundaries. This justifies minimizing over splits and adding both subproblem costs.

For n matrices, there are O(n²) intervals and O(n) splits per interval: O(n³) time and O(n²) cache space, with O(n) recursion depth. Bottom-up evaluation grows interval length so both shorter pieces are ready.

This is not the same pattern as weighted interval scheduling, despite the word “interval.” That problem chose compatible appointments from a suffix; this problem partitions one sequence into recursively combined spans.

Analogy limit: not every interval problem has independent pieces. Your combine rule must account for every interaction across the split.

No. If equal-sized intermediate results can have different future costs depending on representation, preserve that boundary information in the state or prove a single representation dominates.