HouseRobbe_198

https://leetcode.com/problems/house-robber/

image.png

（图片来源https://leetcode.com/problems/house-robber/

）

留意下：
res[i] = max(res[i-2]+num[i], res[i-1])
有点类似斐波那契问题。

 /** 遍历 */
    public int rob(int[] nums) {
        if(nums == null || nums.length <= 0) {
            return 0;
        }

        int[] memo = new int[nums.length+1];
        memo[0] = 0;
        memo[1] = nums[0];

        for(int i=1; i<nums.length ; i++) {
            memo[i+1] = Math.max(memo[i], memo[i-1]+nums[i]);
        }

        return memo[nums.length];
    }

    /** 遍历 */
    public int rob2(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        int prev1 = 0;
        int prev2 = 0;
        for (int num : nums) {
            int tmp = prev1;
            prev1 = Math.max(prev2 + num, prev1);
            prev2 = tmp;
        }

        return prev1;
    }

    /** 暴力递归 */
    public int rob1(int[] nums) {

        return helper(nums, nums.length - 1);
    }

    private int helper(int[] nums, int i) {
        if (i < 0) {
            return 0;
        }

        return Math.max(helper(nums, i - 2) + nums[i], helper(nums, i - 1));
    }