[LeetCode]Falling Squares

O(n^2)的DP可以解决，我们用DP[i]表示对应i位置的square下落之后的高度，positions[i]表示对应i顺序落下的square。那么我们有递推公式：

• DP[i] = max(DP[j]) + positions[i].second, 其中j满足条件square i和square j在x轴上相交

我们知道每一个square下落之后的高度，我们维护一个最大值即可。时间复杂度O(n^2)，空间复杂度O(n)，代码如下：