/**
 * @author wuze
 * @desc ...
 * @date 2021-03-22 16:44:58
 */
public class 打家劫舍2_环形列表_213 {
    /*
    与198 打家劫舍1 区别就是那一题是单列表的形式，本题是环形列表的形式。
    成环就要考虑头尾元素！
    情况一：考虑头元素不考虑尾元素
    情况二：考虑尾元素不考虑头元素
    Math.max(情况一，情况二)
    */
    public int rob(int[] nums) {

        if(nums==null){
            return 0;
        }
        if(nums.length==1){
            return nums[0];
        }

        //当元素值大于2时，就要考虑 情况一、情况二 两种情况了
        //start为开始元素，end为结束元素
        int resultOne = selectTwo(nums,0,nums.length-2);
        int resultTwo = selectTwo(nums,1,nums.length-1);

        return Math.max(resultOne,resultTwo);
    }


    //start为开始元素，end为结束元素
    int selectTwo(int nums[],int start,int end){
        //注意：如果只有两个元素，不管情况一还是情况二都会start==end，这是要return
        if(start==end){
            return nums[start];
        }

        int dp[]=new int[nums.length];
        //头号元素start
        dp[start]=nums[start];
        //start+1位置元素 为 dp[start]和nums[start+1] 中较大者
        dp[start+1]=Math.max(dp[start],nums[start+1]);

        if(nums.length==2){
            return dp[1];
        }

        /*
            /*
    动态规划！
    思路：
如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第 k 间房屋，有两个选项：
 1、偷窃第 k 间房屋，那么就不能偷窃第 k−1 间房屋，偷窃总金额为前 k−2 间房屋的最高总金额与第 k 间房屋的金额之和。
 2、不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额。
在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 k 间房屋能偷窃到的最高总金额。
用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：
                dp[i]=max(dp[i−2]+nums[i],dp[i−1])
    */


        //这个动态规划的状态转移方程就跟之前的 “打家劫舍1” 一样了！
        //从start+2位置元素开始
        //end位置元素可以包含
        for(int i=start+2;i<=end;i++){
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[end];
    }
}