Leetcode 740.删除并获得点数（动态规划，打家劫舍变形）

解题思路：本题可以看作打家劫舍（Leetcode198）的变形。先来看一下打家劫舍的原题：

Leetcode198.打家劫舍：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

可以看出使用动态规划，dp[i]表示按照数组顺序偷到第i家时能获得的最高金额。由于不能偷窃连续的两家，因此状态转移方程为：dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])。
再来看一下本题：

Leetcode740.删除并获得点数：给你一个整数数组 nums ，你可以对它进行一些操作
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1和nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

可以理解为，若偷窃了nums[i]，则金额为nums[i-1]和nums[i+1]的房屋都不能偷窃，同时金额为nums[i]的房屋可能有多家且可以同时偷窃，并且房屋金额乱序。因此，需要对原数组进行处理，新的数组all[i]表示金额为i的房屋的数量。dp[i]表示从0开始递增偷窃到金额i的房屋时能获得的最大金额。状态转移方程为：dp[i] = Math.max(dp[i-1], dp[i-2] + i * all[i])。

//dp
//打家劫舍变形
//必须删除每个等于 nums[i] - 1 和 nums[i] + 1 的元素。
class Solution {
    public int deleteAndEarn(int[] nums) {
        int i;
        int len = nums.length;
        int max=nums[0];
        for(i=1;i<len;i++){
            max = Math.max(max,nums[i]);
        }
        int all[] = new int[max+1];
        for(i=0;i<len;i++){
            all[nums[i]]++;
        }
        int dp[] = new int[max+1];
        dp[0]=0;
        dp[1]=all[1];
        for(i=2;i<=max;i++){
            dp[i] = Math.max(dp[i-1], dp[i-2]+i*all[i]);
        }
        return dp[max];
    }
}