C++刷leetcode（740. 删除与获得点数***）【动态规划】【问题转化】
题目描述：给定一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums ，删除它并获得 nums 的点数。之后，你必须删除每个等于 nums - 1 或 nums + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1:
输入: nums =
输出: 6
解释:
删除 4 来获得 4 个点数，因此 3 也被删除。
之后，删除 2 来获得 2 个点数。总共获得 6 个点数。
示例 2:
输入: nums =
输出: 9
解释:
删除 3 来获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。
注意:
nums的长度最大为20000。
每个整数nums的大小都在范围内。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/delete-and-earn
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
//将问题变型(打家劫舍)
int max_num = *max_element(nums.begin(), nums.end());
vector<int>store(max_num+1, 0);
for(auto num: nums){
store++;
}
//动态规划
int len = store.size();
vector<int>dp(len, 0);
dp = store;
for(int i = 2; i < len; i++){
dp = max(dp, dp + store * i);
}
return dp;
}
}; {:10_329:}
页:
[1]