leetcode 213. House Robber II 入室抢劫抢劫问题 + 一道经典的DP动态规划问题

柔情只为你懂 2022-06-08 09:24 229阅读 0赞

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

本题是上一道题[leetcode 740. Delete and Earn 动态规划DP][leetcode 740. Delete and Earn _DP]、[leetcode 198. House Robber入室抢劫 DP求解][leetcode 198. House Robber_ DP] 和 [leetcode 337. House Robber III DP动态规划 + DFS深度有限遍历][leetcode 337. House Robber III DP_ _ DFS] 的一个简单的变形，不过上一题是一个数组，本题是一个环。

这个问题转化为上一道题的问题就是，因为第一个element 和最后一个element不能同时出现. 则分两次call House Robber I.

case 1: 不包括最后一个element.

case 2: 不包括第一个element.

代码如下：

/*
     * http://blog.csdn.net/xudli/article/details/45886721
     * 
     * */
    public class Solution 
    {
        public int rob(int[] nums) 
        {
            //特殊情况处理
            if(nums==null || nums.length<=0)
                return 0;
            else if(nums.length==1)
                return nums[0];
            else if(nums.length==2)
                return Math.max(nums[0], nums[1]);
            else 
            {
                /*
                 * 因为第一个element 和最后一个element不能同时出现. 则分两次call House Robber I. 
                 * case 1: 不包括最后一个element. 
                 * case 2: 不包括第一个element.
                 * 两者的最大值即为全局最大值
                 * 
                 * */
                int a=robChoose(nums,0,nums.length-2);
                int b=robChoose(nums,1,nums.length-1);
                return Math.max(a, b);
            }
        }
    
        private int robChoose(int[] nums, int begin, int end) 
        {
            int len=end-begin+1;
            int []dp=new int[len];
            dp[0]=nums[begin];
            dp[1]=Math.max(nums[begin], nums[begin+1]);
            for(int i=2;i<len;i++)
            {
                dp[i]=Math.max(dp[i-1], nums[begin+i]+dp[i-2]);
            }
            return dp[len-1];
        }
    }

下面是C++的做法，就是做两次DP动态规划即可

代码如下：

#include <iostream>
    #include <vector>
    #include <queue>
    #include <stack>
    #include <string>
    #include <set>
    #include <map>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int rob(vector<int>& nums)
        {
            if (nums.size() <= 0)
                return 0;
            else if (nums.size() == 1)
                return nums[0];
    
            int a = getRes(nums, 0, nums.size() - 2);
            int b = getRes(nums, 1, nums.size() - 1);
            return max(a, b);
        }
    
        int getRes(vector<int>a, int beg, int end)
        {
            int len = end - beg + 1;
            vector<int>dp(len, 0);
            if (len == 0)
                return 0; 
            dp[0]=a[beg];
            dp[1] = max(a[beg], a[beg + 1]);
            for (int i = beg + 2; i <= end; i++)
                dp[i-beg] = max(dp[i-beg - 1], a[i] + dp[i-beg - 2]);
            return dp[len - 1];
        }
    };

[leetcode 740. Delete and Earn _DP]: http://blog.csdn.net/jackzhang_123/article/details/78895001
[leetcode 198. House Robber_ DP]: http://blog.csdn.net/jackzhang_123/article/details/78037840
[leetcode 337. House Robber III DP_ _ DFS]: http://blog.csdn.net/jackzhang_123/article/details/78151637