题解 | 打家劫舍(一)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int rob (int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length < 3) {
            return Math.max(nums[0], nums[1]);
        }
       int[] data = new int[nums.length];
        // write code here
        return robSolve(nums, nums.length - 1,data);
    }

    public int robSolve (int[] nums, int n, int[] data) {
        if (n < 0) {
            return 0;
        }
        if (n < 2) {
            return nums[n];
        }
        // write code here


        if (n < 0) {
            return 0;
        }
        if (n < 2) {
            return nums[n];
        }
        if (data[n] != 0) {
            return data[n];
        }
        int max = Math.max(Math.max(robSolve(nums, n - 1, data), robSolve(nums, n - 2,
                                    data) + nums[n]),
                           robSolve(nums, n - 3, data) + nums[n]);

        data[n] = max;
        return max;
    }
}