algorithm - 使用 dp 在 O(n^2) 中查找子集的所有连续总和

Question

问题:

给定 n 个数字 𝒙𝟏,𝒙𝟐,…,𝒙𝒏，考虑计算 𝒅[𝒊,𝒋]=𝒙𝒊+𝒙𝒊+𝟏⋯𝒙𝒋 的问题，对于所有 𝒊<=𝒋。通过独立计算每个 𝒅[𝒊,𝒋] 的朴素算法将花费 𝚯(𝒏^𝟑) 时间。在 𝐎(𝒏^𝟐) 时间内推导出解决这个问题的有效方法。

我试着画了一个二维表，行和列都是1~n，并找到了一些公式来填充所有表(上三角)。但我认为每个 block 都是不规则的，也许这不是个好主意。有什么想法吗？谢谢。

Answer 1

是的，您使用二维表(仅上三角)的想法是正确的。然后，您只需要注意:

还有那个

您表格的每个输入因此将在 O(1) 中计算，整个上三角在 O(n^2) 中计算