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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int rob (int[] nums) {
        // write code here
        // 动态规划 - dp[i]表示偷到第i家（偷or不偷）的最大收益
        // 注意！由于是循环数组，因此需要通过【分类讨论】的方式将其拆成【若干不循环数组】的情况，仿照【打家劫舍（一）】的套路解决即可

        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        // case1 - 偷0号，不偷n-1号
        int[] dp1 = new int[n];
        // 偷0号
        dp1[0] = nums[0];
        for (int i = 1; i < n - 1; i++) {
            // 选择偷i号的收益
            int yes = nums[i];
            if (i - 2 >= 0) {
                // i位置本身的金额，加上i-2处的最大收益
                yes += dp1[i - 2];
            }
            // 选择不偷i号的收益
            int no = 0;
            if (i - 1 >= 0) {
                // i-1位置本身的最大收益
                no += dp1[i - 1];
            }
            // i位置的最大收益为偷or不偷两种情况收益的最大值
            dp1[i] = Math.max(yes, no);
        }
        // 不偷n-1号
        dp1[n - 1] = dp1[n - 2];

        // case2 - 不偷0号，偷n-1号
        int[] dp2 = new int[n];
        // 不偷0号
        dp2[0] = 0;
        for (int i = 1; i < n - 1; i++) {
            // 选择偷i号的收益
            int yes = nums[i];
            if (i - 2 >= 0) {
                // i位置本身的金额，加上i-2处的最大收益
                yes += dp2[i - 2];
            }
            // 选择不偷i号的收益
            int no = 0;
            if (i - 1 >= 0) {
                // i-1位置本身的最大收益
                no += dp2[i - 1];
            }
            // i位置的最大收益为偷or不偷两种情况收益的最大值
            dp2[i] = Math.max(yes, no);
        }
        // 偷n-1号
        dp2[n - 1] = dp2[n - 3] + nums[n - 1];

        // 返回两种分类讨论的最大值
        return Math.max(dp1[n - 1], dp2[n - 1]);
    }
}