graph - 与动态规划有关的困惑

Question

我正在浏览与动态编程相关的这个页面。我对给定的复杂性感到非常困惑

在第三种情况下，复杂度为 $O(n^2)$。我不确定它是怎么变成这样的。任何人都可以请详细说明。这里的复杂性是如何计算的。

Answer 1

如果 i 和 j 的范围都在 1 到 n 之间，我可以通过考虑将 i 固定在 1 而 j 从 1 到 n 的范围来查看 n^2 个子问题。然后对 i 1-n 的所有值执行相同的操作。但是图片和集合符号似乎暗示 j > i （一个连续的、唯一的集合），所以我认为这让它有点混乱。我在想象 i=2, j=1... 可以是 x2, x3 （将 j 解释为我们想要从 2 开始的 x 的数量？）或 x2, x1 （将 j 解释为索引）...。