Java描述 LeetCode，213. House Robber II

大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞是我的最大动力。

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 3:

Input: nums = [1,2,3]
Output: 3

Constraints:
1 <= nums.length <= 100
0 <= nums[i] <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber-ii

作为打家劫舍第二个，相比于前一个多了一个限制条件，nums[]数组形成了一个环型，第一个num和最后一个num成为了邻居，也就是说，第一个和最后一个只能选择1个。
我的idea，我本来想用一个flag[]数组代表每一个最优dp[] 是否选择了第一个，到最后一个的时候再进行判断，发现实现起来比较复杂，特别是出现了两个值相等的情况，感觉很难解决，我思维就定在了这里，于是这道题没有解决出来。参考了答案，答案是将大问题分成了两个子问题，既然题目说是第一个和最后一个只能选择一个，那么就可以把问题分成两个情况[0,n-2] 和[1,n-1] 这两种情况，分别对其进行求解，得出的结果取最大值即可。

略，和House Robber问题一样，可以参考上一篇blog，链接：https://blog.csdn.net/qq_41376740/article/details/121006451

public static int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) {
        return nums[0];
    }
    if (n == 2) {
        return Math.max(nums[0], nums[1]);
    }
    //
    return Math.max(rob2(nums, 0, n - 2), rob2(nums, 1, n - 1));
}


public static int rob2(int[] nums, int start, int end) {
    int first = nums[start];
    int second = Math.max(nums[start], nums[start + 1]);
    for (int i = start + 2; i <= end; i++) {
        int current = Math.max(second, first + nums[i]);
        first = second;
        second = current;
    }
    return second;
}

这道题的关键在于，能不能想到将大问题划分成两个子问题了，我是没想到的。哈哈，笨，就当是个积累过程吧！加油呀，河海哥，有错误还请指正，谢谢，么么叽。