LeetCode-213. 打家劫舍 II-蒲公英云

LeetCode-213. 打家劫舍 II

题目思路

这道题目和198.打家劫舍是差不多的，唯一区别就是成环了。(基本和打家劫舍I类似，就是多写了几行代码)
https://donglin.blog.csdn.net/article/details/129648387
对于一个数组，成环的话主要有如下两种情况：
在这里插入图片描述

递归

class Solution {
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        if(nums.length ==1){
            return nums[0];
        }
        //求出第一种情况的答案，要首不要尾
        int ans1 = dfs(nums,0,nums.length-2);
        //求出第二种情况的答案，要尾不要首
        int ans2 = dfs(nums,1,nums.length-1);
        return Math.max(ans1,ans2);
    }
    private int dfs(int[] nums,int start,int end){
        //如果没有了，就返回0
        if(start > end){
            return 0;
        }
        //如果相等 说明只有一个 返回当前就好了
        if(start == end){
            return nums[start];
        }
        //偷
        int stealy = nums[start] + dfs(nums,start+2,end);
        //不偷
        int stealn = dfs(nums,start+1,end);
        return Math.max(stealy,stealn);
    }
}

在这里插入图片描述

动态规划

class Solution {
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        if(nums.length ==1){
            return nums[0];
        }
        int left = allRob(nums,0,nums.length-2);  //情况一
        int right = allRob(nums,1,nums.length-1);  //情况二
        return Math.max(left,right);
    }
    // 198.打家劫舍的逻辑
    private int allRob(int[] nums,int start,int end){
        if(start == end){
            return nums[end];
        }
        int[] dp = new int[nums.length];
        dp[start] = nums[start];
        dp[start+1] = Math.max(nums[start],nums[start+1]);
        for(int i = start+2;i<=end;i++){
            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[end];
    }
}