algorithm - TopCoder 解决方案与动态规划解决方案

Question

我正在尝试解决这个顶级编码器问题。看了解法分析还是看不懂。

解决方案的基本思路是逆向思考，插入元素而不是删除。但这如何降低问题的复杂性？

我明白这是一个动态规划问题。我在维基百科上读到，DP问题避免重复解决子问题，从而降低复杂性。但我在这里没有看到任何子问题冗余。

谢谢

问题陈述 星之匣 (原文如此) 是东方宇宙中的一个装置。其目的是快速产生能量。最初它包含连续的 n 颗星。星星从左到右标记为 0 到 n-1。给你一个 int[] 权重，其中 weight[i] 是第 i 颗星的权重。

以下操作可以重复使用来产生能量:

Choose a star x other than the very first star and the very last star.
The x-th star disappears.
This generates weight[x-1] * weight[x+1] units of energy.
We decrease n and relabel the stars 0 through n-1 from the left to the right.

您的任务是使用设备产生尽可能多的能量单位。返回尽可能多的生成能量总量。

Answer 1

子问题 f(start,end) 是计算删除范围 [start,end] 内的所有内部恒星可以获得的最大能量。 (内星是除端点之外的任何星。)

有 n 颗星，所以大约有 n*n/2 个这些子问题。

原题是start=0，end=n-1的子题的答案。

子问题可以通过考虑最后一个要删除的节点的所有选择来解决。对于每个选择x，我们加上删除x之前的星星的成本f(start,x)，删除x之后的星星的成本f(x,end)，以及删除x的成本weight[start]*weight[end]本身。

这需要 O(end-start) 操作，所以整个问题可以在 O(n^3) 中解决