题目链接

思路

分析动态规划题目的时候只需要考虑最后一个阶段，因为所有的阶段转化都是相同的，考虑最后一个阶段容易发现规律

在数组的动态规划问题中，一般 dp[i] 都是表示以 nums 以前 i 个元素组成（即 nums[i - 1]）的状态；dp[i][j] 分别表示以 nums1 前 i 个元素（即 nums1[i - 1]）组成和以 nums2 前 j 个元素（即 nums2[j - 1]）组成的状态，以此类推

字符串也是个数组，是字符数组

表示状态

状态表示就是靠猜，但是会有猜的套路，一般都是通过最终结果和数组数量来猜

先上结论：\(dp[i]\) 表示到数字 i 为止能获得的最大点数

这个题的状态表示很有意思，大部分的状态表示是到 \(nums\) 前 i 个数为止的状态，即让 \(nums\) 的下标作为存取状态的索引，但这个题是让 \(nums\) 的值作为存取状态的索引，还是比较难想到的

找状态转移方程

思考的方向是：大问题的最优解怎么由小问题的最优解得到

边界处理

空间优化

代码

`dp`数组版

class Solution {
    public int deleteAndEarn(int[] nums) {
        // 打表存储每个元素的总和
        int[] sum = new int[10001];
        for (int num : nums) {
            sum[num] += num;
        }

        // dp[i] 表示到数字 i 能取得的分数最大值
        int[] dp = new int[10001];
        int result = 0;
        dp[1] = sum[1];
        for (int i = 2; i <= 10000; i++) {
            // 分为两种情况
            // 1.不选择数字 i
            // 2.选择数字 i,舍弃数字 i - 1
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + sum[i]);
            result = Math.max(result, dp[i]);
        }

        return result;
    }
}

空间优化版

class Solution {
    public int deleteAndEarn(int[] nums) {
        // 打表存储每个元素的总和
        int[] sum = new int[10001];
        for (int num : nums) {
            sum[num] += num;
        }

        int prevMax = 0;
        int currMax = 0;
        for (int i = 1; i <= 10000; i++) {
            int temp = currMax;
            // 分为两种情况
            // 1.不选择数字 i
            // 2.选择数字 i,舍弃数字 i - 1
            currMax = Math.max(currMax, prevMax + sum[i]);
            prevMax = temp;
        }

        return currMax;
    }
}