198. House Robber

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

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

/** 遍历 */
    public int rob(int[] nums) {
        if(nums == null || nums.length < 1) {
            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 == null || nums.length < 1) {
            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));
    }