[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)，代码如下：

	class Solution {
	public:
	vector<int> fallingSquares(vector<pair<int, int>>& positions) {
	int len = positions.size(), globalMax = 0;
	vector<tuple<int, int, int>> intervals;
	vector<int> res;
	for(int i = 0; i < positions.size(); ++i)
	{
	int maxHeight = positions[i].second;
	for(int j = 0; j < i; ++j)
	{
	if(overlap(positions[i].first, positions[i].first + positions[i].second - 1, get<0>(intervals[j]), get<1>(intervals[j])))
	{
	maxHeight = max(get<2>(intervals[j]) + positions[i].second, maxHeight);
	}
	}
	globalMax = max(maxHeight, globalMax);
	res.push_back(globalMax);
	intervals.push_back(make_tuple(positions[i].first, positions[i].first + positions[i].second - 1, maxHeight));
	}
	return res;
	}
	private:
	bool overlap(int a, int b, int c, int d)
	{
	return !(a > d || b < c);
	}
	};

view raw Falling Squares.cpp hosted with ❤ by GitHub