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

剑指 Offer II 089. 房屋偷盗【中等题】

思路：【动态规划】

只要找出转移方程就不难，有两种写法，一种是dp数组，一种是滚动数组。

代码：【dp数组】

class Solution {
    
    public int rob(int[] nums) {
    
        int n = nums.length;
        //排除特殊情况
        if (n == 1){
    
            return nums[0];
        }
        //定义dp数组 dp[i]表示 走到第i号房屋时，能够偷到的最高金额
        int[] dp = new int[n];
        //dp[0] 和 dp[1]赋初值
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for (int i = 2; i < n; i++) {
    
            //动态转移方程
            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        //返回走到最后一个房屋时，能够偷到的最大金额
        return dp[n-1];
    }
}

代码：【滚动数组】

class Solution {
    
    public int rob(int[] nums) {
    
        int n = nums.length;
        //排除特殊情况
        if (n == 1){
    
            return nums[0];
        }
        //定义滚动数对 a 和 b 表示走到某间房屋时，能够偷到的最大金额
        //a 和 b 紧邻且a在b左侧 首先为 a 和 b 赋初值
        int a = nums[0];
        int b = Math.max(nums[0],nums[1]);
        for (int i = 2; i < n; i++) {
    
            //动态转移方程,c表示紧邻b房间在b右侧的房间能偷到的最大金额
            int c = Math.max(a+nums[i],b);
            a = b;
            b = c;
        }
        //返回走到最后一个房屋时，能够偷到的最大金额
        //由于滚动到最后一位时，b会更新为c，而c是局部变量，所以这里返回b即可
        return b;
    }
}

---

剑指 Offer II 090. 环形房屋偷盗【中等题】

思路：【动态规划】

与上题思路一致，但要把端点处分为两种情况考虑，由于题目限制，当你从第0家开始偷，就只能在第n-2家结束；从第1家开始偷，则可以在第n-1家结束。

代码：【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]);
        }
        //定义dp数组 dp[i]表示 走到第i号房屋时，能够偷到的最高金额
        int[] dp = new int[n];
        //dp[0] 和 dp[1]赋初值 两种情况 从第0间开始偷 则 必不能选第n-1间 从 第1间开始偷，则可以选择第n-1间
        //1
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for (int i = 2; i < n; i++) {
    
            //动态转移方程
            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        //第1种情况的最大偷盗金额，存入ans
        int ans = dp[n-2];
        //2
        dp[1] = nums[1];
        dp[2] = Math.max(nums[1],nums[2]);
        for (int i = 3; i < n; i++) {
    
            //动态转移方程
            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        //求出第2种情况的最大偷盗金额后更新ans
        ans = Math.max(ans,dp[n-1]);
        return ans;
    }
}

代码：【滚动数组】

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]);
        }
        //定义滚动数对 a 和 b 表示走到某间房屋时，能够偷到的最大金额
        //a 和 b 紧邻且a在b左侧 首先为 a 和 b 赋初值
        int a = nums[0];
        int b = Math.max(nums[0],nums[1]);
        for (int i = 2; i < n; i++) {
    
            //动态转移方程,c表示紧邻b房间在b右侧的房间能偷到的最大金额
            int c = Math.max(a+nums[i],b);
            a = b;
            b = c;
        }
        //遍历结束时，a为第n-2位的最大偷盗金额 b 为第n-1位的最大偷盗金额
        //第1种情况的最大偷盗金额在第n-2位，存入ans
        int ans = a;
        //2
        a = nums[1];
        b = Math.max(nums[1],nums[2]);
        for (int i = 3; i < n; i++) {
    
            //动态转移方程
            int c = Math.max(a+nums[i],b);
            a = b;
            b = c;
        }
        //第2种情况的最大偷盗金额在第n-1位，更新ans
        ans = Math.max(ans,b);
        //返回两种最大偷盗金额的最大值
        return ans;
    }
}