dp练习题

先来一个简单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];
    }

};