题解 | #打家劫舍(二)#

import java.util.*;


public class Solution {
    //如果0位置偷，在2-n-2的区域内与打家劫舍1相同 =》nums[0] ,rob1(2,n-2)
    //如果0位置不偷，就是1-n-1位置进行打家劫舍1. =>
    //rob1(1,n-1);
    // f[i] 表示偷的最大金额，g[i] 表示不偷的最大金额


    public int rob (int[] nums) {
        int n = nums.length;

        return Math.max(nums[0] + rob1(nums,2,n-2),rob1(nums,1,n-1));
    }

    //与打家劫舍1逻辑一致

    public int rob1(int[]nums,int start,int end){

        if(start>end) return 0;

        int n = nums.length;
        int[] f= new int [n];
        int[] g = new int [n];
        //1.初始化
        f[start] = nums[start];
        //2.填表：只用start -end 
        for(int i =start +1;i<=end; i++){

            f[i] = nums[i] +g[i-1];
            g[i] = Math.max(g[i-1],f[i-1]);
        }

        return Math.max(f[end],g[end]);
    }
}