LeetCode740 删除并获得点数(Medium)
题目叙述：
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1：
输入：nums = [3,4,2]
输出：6
解释：
你可以执行下列步骤：
- 删除 4 获得 4 个点数，因此 3 也被删除。nums = [2]。
- 之后，删除 2 获得 2 个点数。nums = []。
总共获得 6 个点数。
示例 2：
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
你可以执行下列步骤：
- 删除 3 获得 3 个点数。所有的 2 和 4 也被删除。nums = [3,3]。
- 之后，再次删除 3 获得 3 个点数。nums = [3]。
- 再次删除 3 获得 3 个点数。nums = []。
总共获得 9 个点数。
提示：
1 <= nums.length <= 2 * 1041 <= nums[i] <= 104
题解
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
if (nums.empty()) return 0;
int maxVal = *max_element(nums.begin(), nums.end());
vector<int> sum(maxVal + 1, 0);
for (int x : nums) {
sum[x] += x;
}
// 定义 dp[i]：只考虑数字 0 到 i，能获得的最大点数
// dp[0] = 0（数字0不存在）
// dp[1] = sum[1]（只有一个数字1时，拿了就是它的总分）
vector<int> dp(maxVal + 1, 0);
dp[1] = sum[1];
for (int i = 2; i <= maxVal; ++i) {
// 情况1：不拿 i -> 结果就是 dp[i-1]
// 情况2：拿 i -> i-1 必须删除，所以只能看 i-2 的结果，再加 i 的分
dp[i] = max(dp[i - 1], dp[i - 2] + sum[i]);
}
return dp[maxVal];
}
};
流程
首先是看函数Body，给了一个Vector<int> nums，
-
首先是判空。
nums.size !=0 -
找到nums里的最大值 去维护一个数组。
为什么要用nums数组的最大值去维护数组呢，我们采用这样的方式：
vector<int> sum的 下标即为值，然后sum[idx]即为idx的总和。
// 也就是这样
vector<int> sum(maxVal + 1, 0);
for (int x : nums) {
sum[x] += x; // 相同值累加，因为选了 x 就能拿走所有 x
}
这样，我们就拿到了一个sum的vector，其核心是存储对应下标对应的Credit，它根据index进行归一化，把Credit * 次数来对应sum[idx]的值。
接下来就是应用经典的打家劫舍思路进行动态规划处理。
题解里有一个注释值得分析
// 定义 dp[i]：只考虑数字 0 到 i，能获得的最大点数
// dp[0] = 0（数字0不存在）
// dp[1] = sum[1]（只有一个数字1时，拿了就是它的总分）
这就是打家劫舍里的选或不选的问题，先遍历sum数组。最优值）。
vector<int> dp(maxVal + 1, 0);
dp[1] = sum[1];
for (int i = 2; i <= maxVal; ++i) {
// 情况1：不拿 i -> 结果就是 dp[i-1]
// 情况2：拿 i -> i-1 必须删除，所以只能看 i-2 的结果，再加 i 的分
dp[i] = max(dp[i - 1], dp[i - 2] + sum[i]);
// 不拿i //拿了i，也就是加sum[i]，同时也略过了i - 1
}
return dp[maxVal];
现在我们来看for以及for前的处理。
- 定义
dp[i]：只考虑数字 0 到 i，能获得的最大点数，先把初始状态赋值给sum[1]，也就是dp[1]。
然后根据for循环，从index = 2 到index <= maxVal，每次循环更新都动态判断max(dp[i - 1], dp[i - 2] + sum[i])
当然决定拿还是不拿由std::max决定，毕竟我们的目标是获得最大点数。
一次循环之后填充了dp，自然最后dp[maxVal] 是我们获得到的最大值。
其实它的思想精髓在迭代，我们从sum的数组得到了每个值对应的总Credit，然后遍历sum数组进行动态规划。
// dp[0] = 0（数字0不存在）
// dp[1] = sum[1]（只有一个数字1时，拿了就是它的总分）
用这两个状态来维护初始值，因为sum的index是nums的值，不是单纯的index。 也就是前面说的 定义 dp[i]：只考虑数字 0 到 i，能获得的最大点数。
所以在i + 1,i + 2 i + … 的时候，都会参考到前面的结果动态来判断全局的最大Credit。