Matrix chain multiplication

矩阵链乘法，找出进行操作最少的加括号方式。使用动态规划求解，利用分治的思想。

对于乘法 ABCD，取 A(BCD), (AB)(CD), (ABC)D 三种情况的最小值，子问题递归求解。

相关题目

LeetCode 312. Burst Balloons

等价于一个矩阵链乘问题。

from functools import cache


def maxCoins(self, nums: List[int]) -> int:
    nums.insert(0, 1)
    nums.append(1)

    @cache
    def rec(left, right):
        if left >= right:
            return 0
        return max((rec(left, i) + rec(i + 1, right) + nums[left - 1] * nums[i] * nums[right])
                   for i in range(left, right))
    return rec(1, len(nums) - 1)