36.打家劫舍(题号：198)

public class HouseRobber {
    //方法一：动态规划
    public int rob1(int[] nums) {
        int n = nums.length;
        //特殊情况
        if(nums==null||n==0){
            return 0;
        }

        //定义状态，将前i个房屋能偷到的最大金额保存到dp[i]中
        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];
    }
    //方法二：空间优化
    public int rob(int[] nums) {
        int n = nums.length;
        //特殊情况
        if(nums==null||n==0){
            return 0;
        }


        //定义初始状态
        int pre2 = 0;
        int pre1 = nums[0];


        //遍历状态，依次转移
        for (int i = 1; i <n; i++) {
            int curr = Math.max(pre1,pre2+nums[i]);
            pre2 = pre1;
            pre1 = curr;
        }

        return pre1;
    }

    public static void main(String[] args) {
        int[] nums = {2,7,9,3,1};
        HouseRobber houseRobber = new HouseRobber();
        System.out.println(houseRobber.rob(nums));
    }
}