🟡 剑指 Offer II 090. 环形房屋偷盗

LeetCode 提示

题目难度 中等

原题链接 🔗 leetcode

题解1

关键在于怎么避免首尾相连的问题。

不相连的情况就很简单，直接dp

相连的情况，通过控制可以dp的上下界，就可以转换成不相连的情况了

抄作业

class Solution {    public 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(robRange(nums, 0, n-1), robRange(nums, 1, n));    }
    public int robRange(int[] nums, int lo, int hi) {        int[] dp = new int[]{nums[lo], Math.max(nums[lo], nums[lo+1])};        int tmp=0;
        for (int i=lo+2; i<hi; i++) {            tmp = dp[1];            dp[1] = Math.max(dp[1], dp[0]+nums[i]);            dp[0] = tmp;        }
        return dp[1];    }}