740. Delete and Earn

 /*
    这个题的关键在于：要想达到最好的结果，每次都应该选取合适的数，当选取一个数时由于要考虑它两边的数，所以我们采取装桶法，
    这样就知道数组中所有这个数相加的和（也就是当选取一个数时会获得的利益，和抛弃一个数时的损失），同时也相当于桶排序了，可以直接表示出i相邻的数。
    转化为子问题，子问题就是子序列，最小的子序列就是只有一个数，最大的子序列就是所有数，也就是最后答案，我们一个一个加
    新序列就是原序列添加一个数，这里我们倒着考虑，从最后一个数往前添加，假设原序列的最好结果是dp[i+1]，那么新序列生成后，
    有两种情况，就是新添加的数取不取，对应状态方程就是：
    dp[i] = Math.max(valus[i]+dp[i-2],dp[i-1])，括号中第一个选项是取新数，这样的话i+1就不能取，新的结果就是现在的数加上i+2的情况，
    这里能直接使用dp[i+2]是因为i+1不取，所以i+2可以任选取不取，符合使用条件。
    如果不取新数，那么现在的状态就是dp[i+1]
     */
    public int deleteAndEarn(int[] nums) {
        //假设有很多桶，数组中的每个数就是桶的编号，桶里装的就是数组中所有等于桶编号的数的和
        int[] dp = new int[10003];
        int[] valus = new int[10001];

        //装桶环节
        for(int num : nums)
        {
            valus[num] += nums[num];
        }
        //
        for(int i = 2;i < 10003;i++)
        {
            //dp[i]记录倒着数，到i位置处的子序列的最好结果是什么，注意这里dp[i]产生的条件是不考虑前边，也就是i-1处桶，以后要用到的话，也要保证i-1处桶不用才能成立
            //状态方程：考虑要不要i桶，不要的话，dp[i+1]满足成立条件，此时的最好情况也就是dp[i+1]。如果要i,那么i+1不能要，但是dp[i+2]满足成立条件
            //最好的结果就是valus[i]+dp[i+2]
            dp[i] = Math.max(valus[i]+dp[i-2],dp[i-1]);
        }
    return dp[10002];
    }