740. Delete and Earn

This question can be reduced to theHouse Robbers questionalso on LeetCode. Please have a look at it if you haven't seen it before.

Observations:

• The order of nums does not matter.
• Once we decide that we want a num , we can add all the occurrences of num into the total.

We first transform thenumsarray into apointsarray that sums up the total number of points for that particular value. A value ofxwill be assigned to indexxinpoints.

nums:[2, 2, 3, 3, 3, 4](2 appears 2 times, 3 appears 3 times, 4 appears once)
points:[0, 0, 4, 9, 4]<- This is the gold in each house!

class Solution {
    public int deleteAndEarn(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] prices = new int[10001];
        for (int num : nums){
            prices[num] += num;
        }

        int[] dp = new int[10001];
        dp[0] = 0;
        dp[1] = prices[1];
        for (int i = 2; i <= 10000; i++){
            dp[i] = Math.max(prices[i] + dp[i - 2], dp[i - 1]);
        }

        return dp[10000];
    }
}

198. House Robber

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        if (n == 1) return nums[0];

        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= n; i++){
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }

        return dp[n];
    }
}

213. House Robber II

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;

        if (n == 1) return nums[0];
        if (n == 2) return Math.max(nums[0], nums[1]);

        return Math.max(helper(nums, 0, n - 2), helper(nums, 1, n - 1));
    }

    private int helper(int[] nums, int start, int end){
        int[] dp = new int[2];
        dp[start % 2] = nums[start];
        dp[(start + 1) % 2] = Math.max(nums[start], nums[start + 1]);

        for (int i = start + 2; i <= end; i++){
            dp[i % 2] = Math.max(dp[(i - 2) % 2] + nums[i], dp[(i - 1) % 2]);
        }

        return dp[end % 2];
    }
}

337. House Robber III

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private class ResultType{
        int rob;
        int not_rob;

        public ResultType(){
            this.rob = 0;
            this.not_rob = 0;
        }
    }
    public int rob(TreeNode root) {
        ResultType ans = helper(root);

        return Math.max(ans.rob, ans.not_rob);
    }

    private ResultType helper(TreeNode root){
        ResultType res = new ResultType();

        if (root == null) return res;

        ResultType leftResult = helper(root.left);
        ResultType rightResult = helper(root.right);

        res.rob = root.val + leftResult.not_rob + rightResult.not_rob;
        res.not_rob = Math.max(leftResult.rob, leftResult.not_rob) + Math.max(rightResult.rob, rightResult.not_rob);

        return res;
    }
}