LeetCode213. House raiding II

This paper is finally updated at 484 Days ago, , The information may have developed or changed .

One 、 Ideas

Compare it with the trade-offs , You can't steal the first house and the last house at the same time . There are more choices , Or steal the first one , Or steal the last home . The dynamic programming problem is to find out the choice among the questions , Get the State .

Two 、 problem

You are a professional thief , Plan to steal houses along the street , There is a certain amount of cash in every room . All the houses in this place are Make a circle , This means that the first house and the last house are next to each other . meanwhile , Adjacent houses are equipped with interconnected anti-theft system , If two adjacent houses are broken into by thieves on the same night , The system will automatically alarm .

Given an array of non negative integers representing the storage amount of each house , Count you Without triggering the alarm device , The maximum amount that can be stolen .

Example  1：

 Input ：nums = [2,3,2]
 Output ：3
 explain ： You can't steal first  1  House No （ amount of money  = 2）, And then steal  3  House No （ amount of money  = 2）,  Because they are next to each other .

Copy

Example 2：

 Input ：nums = [1,2,3,1]
 Output ：4
 explain ： You can steal first  1  House No （ amount of money  = 1）, And then steal  3  House No （ amount of money  = 3）.
      Maximum amount stolen  = 1 + 3 = 4 .

Copy

Example 3：

 Input ：nums = [0]
 Output ：0

Copy

Tips ：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

Related Topics

• Dynamic programming

\n

• 475
• 0

3、 ... and 、 Code

public int rob(int[] nums) {
            if (nums.length == 0) {
                return 0;
            }
            if (nums.length == 1) {
                return nums[0];
            }
            return Math.max(rangeRob(nums, 0, nums.length - 2)
                    , rangeRob(nums, 1, nums.length - 1));
        }

        public int rangeRob(int[] nums, int start, int end) {
            int[][] arr = new int[nums.length][2];
            arr[start][1] = nums[start];
            arr[start][0] = 0;
            for (int i = start + 1; i <= end; i++) {
                arr[i][1] = Math.max(arr[i - 1][0] + nums[i], arr[i - 1][1]);
                arr[i][0] = Math.max(arr[i - 1][0], arr[i - 1][1]);
            }
            return Math.max(arr[end][0], arr[end][1]);
        }

Copy

Post Views: 249