[LeetCode]Delete and Earn

标准的DP类型的题目。我们先从小到大sort input array nums，并且把相同的group在一起得到count数组。比如nums = [4,3,2,1,2,4]就变为count = [(1, 1),(2, 2),(3, 1),(4,2)]，括号内第二个数字代表相同的元素有多少个。我们创建dp数组：

• 定义dp[i][0]为只考虑count的0-i的元素并且不选择位于i的元素情况下的最大值
• 定义dp[i][1]为只考虑count的0-i的元素并且选择位于i的元素情况下的最大值

我们有递推公式：

• 如果count[i].first == count[i-1].first + 1
• dp[i][0] = max(dp[i-1][0], dp[i - 1][1])
• dp[i][1] = max(dp[i - 1][1], dp[i-1][0] + count[i].first * count[i].second)
• else
• dp[i][0] = max(dp[i-1][0], dp[i - 1][1])
• dp[i][1] = max(max(dp[i-1][0], dp[i - 1][1]) + count[i].first * count[i].second)

时间复杂度取决于sort，O(n * log n)，空间复杂度O(n)。这里我们用BST记录count，之后顺序遍历即可，时间复杂度是一样的。代码如下：

	class Solution {
	public:
	int deleteAndEarn(vector<int>& nums) {
	if (nums.empty())return 0;
	map<int, int> cnts;
	for (const auto& num : nums)++cnts[num];
	vector<vector<int>> dp(cnts.size(), vector<int>(2, INT_MAX));
	auto iter = cnts.begin();
	dp[0][0] = 0;
	dp[0][1] = cnts[iter->first] * iter->first;
	int n = cnts.size(), prev = iter->first;
	++iter;
	for(int i = 1; i < n; ++i, ++iter)
	{
	dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
	dp[i][1] = iter->first - prev == 1 ? cnts[iter->first] * iter->first + dp[i - 1][0] : cnts[iter->first] * iter->first + max(dp[i - 1][0], dp[i - 1][1]);
	prev = iter->first;
	}
	return max(dp[n - 1][0], dp[n - 1][1]);
	}
	};

view raw Delete and Earn.cpp hosted with ❤ by GitHub