{"action":"opened","issue":{"url":"https://api.github.com/repos/Shawngbk/Leecode/issues/123","repository_url":"https://api.github.com/repos/Shawngbk/Leecode","labels_url":"https://api.github.com/repos/Shawngbk/Leecode/issues/123/labels{/name}","comments_url":"https://api.github.com/repos/Shawngbk/Leecode/issues/123/comments","events_url":"https://api.github.com/repos/Shawngbk/Leecode/issues/123/events","html_url":"https://github.com/Shawngbk/Leecode/issues/123","id":187798297,"number":123,"title":"213. House Robber II","user":{"login":"Shawngbk","id":18609174,"avatar_url":"https://avatars.githubusercontent.com/u/18609174?v=3","gravatar_id":"","url":"https://api.github.com/users/Shawngbk","html_url":"https://github.com/Shawngbk","followers_url":"https://api.github.com/users/Shawngbk/followers","following_url":"https://api.github.com/users/Shawngbk/following{/other_user}","gists_url":"https://api.github.com/users/Shawngbk/gists{/gist_id}","starred_url":"https://api.github.com/users/Shawngbk/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Shawngbk/subscriptions","organizations_url":"https://api.github.com/users/Shawngbk/orgs","repos_url":"https://api.github.com/users/Shawngbk/repos","events_url":"https://api.github.com/users/Shawngbk/events{/privacy}","received_events_url":"https://api.github.com/users/Shawngbk/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2016-11-07T19:02:17Z","updated_at":"2016-11-07T19:02:17Z","closed_at":null,"body":"Now the question is how to rob a circular row of houses. It is a bit complicated to solve like the simpler question. It is because in the simpler question whether to rob num[lo] is entirely our choice. But, it is now constrained by whether num[hi] is robbed.\r\n\r\nHowever, since we already have a nice solution to the simpler problem. We do not want to throw it away. Then, it becomes how can we reduce this problem to the simpler one. Actually, extending from the logic that if house i is not robbed, then you are free to choose whether to rob house i + 1, you can break the circle by assuming a house is not robbed.\r\n\r\nFor example, 1 -> 2 -> 3 -> 1 becomes 2 -> 3 if 1 is not robbed.\r\n\r\nSince every house is either robbed or not robbed and at least half of the houses are not robbed, the solution is simply the larger of two cases with consecutive houses, i.e. house i not robbed, break the circle, solve it, or house i + 1 not robbed. Hence, the following solution. I chose i = n and i + 1 = 0 for simpler coding. But, you can choose whichever two consecutive ones.\r\nHouse Robber I的升级版. 因为第一个element 和最后一个element不能同时出现. 则分两次call House Robber I. case 1: 不包括最后一个element. case 2: 不包括第一个element.\r\n两者的最大值即为全局最大值\r\n\r\npublic class Solution {\r\n    public int rob(int[] nums) {\r\n        if(nums==null || nums.length==0) return 0;  \r\n        if(nums.length==1) return nums[0];  \r\n        if(nums.length==2) return Math.max(nums[0], nums[1]); \r\n        return Math.max(helper(nums, 0, nums.length - 2), helper(nums, 1, nums.length - 1));\r\n    }\r\n    \r\n     private int helper(int[] nums, int low, int high) {\r\n        int flag = high - low + 1;\r\n        int[] dp = new int[flag];\r\n        dp[0] = nums[low];\r\n        dp[1] = Math.max(nums[low], nums[low+1]);\r\n        for(int i = 2; i < flag; i++) {\r\n            //因为有可能选第一个或者不选第一个所以nums［i＋low］，要加标识，0or1\r\n            dp[i] = Math.max(nums[i+low] + dp[i-2], dp[i-1]);\r\n        }\r\n        return dp[flag-1];\r\n    }\r\n}"}}
{"actor":{"display_login":"Shawngbk"}}