先来一个简单dp练习
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> a(n + 1);
int ans = nums[0]; a[0] = nums[0];
if (n == 1) return ans;
a[1] = max(nums[0], nums[1]);
ans = max(ans, a[1]);
if (n == 2) return ans;
for (int i = 2; i < n; i++) {
a[i] = max(a[i - 1], nums[i] + a[i - 2]);
ans = max(ans, a[i]);
}
return ans;
}
};
我们只需要考虑前面的就行,后面的就交给后面的元素考虑
再来一个类似的题目
这个题目咋一看还没有什么思路,但是我们可以转化为打家劫舍
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
int mmax = 0;
for (auto u : nums) {
mmax = max(mmax, u);
}
vector<int> dp(mmax + 1);
for (auto u : nums) {
dp[u] += u;
}
return fun(dp);
}
int fun(vector<int> nums) {
int n = nums.size();
vector<int> dp(n + 1);
int ans = 0;
ans = dp[0] = nums[0];
if (n == 1) return ans;
dp[1] = max(nums[0], nums[1]);
ans = max(ans, dp[1]);
if (n == 2) return ans;
for (int i = 2; i <= n; i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
ans = max(dp[i], ans);
}
return ans;
}
};
可是如果我们数组里面的数字很大怎么办,我们不能把我们的数组也开的特别大
class Solution {
public:
long long maximumTotalDamage(vector<int>& power) {
unordered_map<int, int> cnt;
for (auto u : power) {
cnt[u]++;
}
vector<pair<int, int>> a(cnt.begin(), cnt.end()); // 拷贝过来,此处很重要
// 需要排序吗
ranges::sort(a);
int n = a.size();
vector<long long> dp(n + 1);
for (int i = 0, j = 0; i < n; i++) {
auto& [x, c] = a[i];
while (a[j].first < x - 2) {
j++;
}
dp[i + 1] = max(dp[i], dp[j] + (long long)x * c);
}
return dp[n];
}
};