力扣740.删除并获得点数

题目

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

解题思路

​ 动态规划----打家劫舍加强版

1.找到原始数组nums中的最大数max

2.建立一个数组all用于记录0-max点数的个数，

例如

all=[0, 0, 2, 3, 1]; all[2]=2,代表点数为2的个数是2，all[4]=1代表点数为4的个数是1

3.将all数组看成是一个打家劫舍问题，选中的数的左右都不能被选，该问题的最优子结构公式

dp[i] = Math.max(dp[i - 1], dp[i - 2] + i * all[i]);

​ ①当前数的前一个数的最有情况

​ ②当前数前两个数的最优情况与当前数相加的总和

情况①②中选最优情况作为该子问题的最优解

代码

class Solution {
    public int deleteAndEarn(int[] nums) {
        if(nums==null && nums.length==0){
            return 0;
        }else if(nums.length==1){
            return nums[0];
        }

        int length=nums.length;
        //获取到nums数组中的最大值
        int max=nums[0];
        for(int i=1;i<length;i++){
            max=Math.max(max,nums[i]);
        }
        //利用最大值确定数组大小
        int[] all=new int[max+1];
        //all数组以点数为下标，存储的是点数对应的个数
        for(int i=0;i<length;i++){
            all[nums[i]]++;
        }
        int[] dp=new int[max+1];
        dp[1]=all[1];
        for(int i=2;i<=max;i++){
            dp[i]=Math.max(dp[i-1],dp[i-2]+all[i]*i);
        }
        return dp[max];
    }
}