528
个编辑
更改
建立内容为“Category:刷题 Category:动态规划 矩阵链乘法，找出进行操作最少的加括号方式。使用动态规划求解，利用分治的思想。…”的新页面
[[Category:刷题]]
[[Category:动态规划]]
矩阵链乘法，找出进行操作最少的加括号方式。使用动态规划求解，利用分治的思想。
对于乘法 ''ABCD''，取 ''A''(''BCD''), (''AB'')(''CD''), (''ABC'')''D'' 三种情况的最小值，子问题递归求解。
<ref>https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/</ref>
== 相关题目 ==
=== [https://leetcode.com/problems/burst-balloons/description/ LeetCode 312. Burst Balloons] ===
等价于一个矩阵链乘问题。
<syntaxhighlight lang=python>
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)
</syntaxhighlight>
== 参考资料 ==
<references />
[[Category:动态规划]]
矩阵链乘法，找出进行操作最少的加括号方式。使用动态规划求解，利用分治的思想。
对于乘法 ''ABCD''，取 ''A''(''BCD''), (''AB'')(''CD''), (''ABC'')''D'' 三种情况的最小值，子问题递归求解。
<ref>https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/</ref>
== 相关题目 ==
=== [https://leetcode.com/problems/burst-balloons/description/ LeetCode 312. Burst Balloons] ===
等价于一个矩阵链乘问题。
<syntaxhighlight lang=python>
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)
</syntaxhighlight>
== 参考资料 ==
<references />