包子君top 5油管中文up主 & Leetcode solution 213. House Robber II

咳咳，标题党一下。。。仅仅是包子君(行者)的最近喜好，不代表包子其他老师。哎，书是读的越来越少了，youtube看的越来越多了，应该是快废了。。。

都不是那种家喻户晓，带货几个亿的大up主啦。

Top 1: 毒角show。

东北老乡，做了很多我想做的事儿，拖鞋大裤衩，球打得好还会rap，小伙子很有前途。

Top 2: 李自然说。

胶东口音我听起来也特别熟悉，牛13 吹得很好

Top 3: 冲浪普拉斯

视频很严谨，小伙子思路很好

Top 4: 跟我一起来谈钱。

一开始姐姐说的挺好，后来有点啰嗦了，比较适合做饭刷碗的时候用2.0x的速度来听

Top 5: 大象放映室。

文案非常好，而且电影风格很符合我伪文青的口味

好了，赶紧做题吧~ 如果你还没有subscribe包子的油管，翻个墙呗兄弟，谢谢！

Leetcode solution 213. House Robber II

Blogger: http://blog.baozitraining.org/2020/06/leetcode-solution-213-house-robber-ii.html

Youtube: https://youtu.be/FZq3YHzvUa4

博客园: https://www.cnblogs.com/baozitraining/p/13128835.html

B站: https://www.bilibili.com/video/BV1k54y1B7mD/

Problem Statement

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

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.

Example 1:

Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
             because they are adjacent houses.

Example 2:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Problem link

Video Tutorial

You can find the detailed video tutorial here

• Youtube
• B站

Thought Process

This is very similar to House Robber I problem where the only difference is the houses now form a circle (French fancy way calls it cul-de-sac). It's same DP algorithm except now we need to consider two cases: whether we rob the first house or not. If we rob the first house, we should not rob the last house. If we do not rob the first house, we can rob the last house. We can even reuse the rob() function in House Robber I problem

Solutions

Use DP

 1 public int rob(int[] nums) {
 2     if (nums == null || nums.length == 0) {
 3         return 0;
 4     }
 5     if (nums.length == 1) {
 6         return nums[0];
 7     }
 8 
 9     // rob first house, so need to remove the last house
10     int[] rob_first_nums = new int[nums.length - 1];
11     for (int i = 0; i < rob_first_nums.length; i++) {
12         rob_first_nums[i] = nums[i];
13     }
14 
15     // do not rob first house, start from the 2nd and rob to the end of the house
16     int[] rob_no_first_nums = new int[nums.length - 1];
17     for (int i = 1; i < nums.length; i++) {
18         rob_no_first_nums[i - 1] = nums[i];
19     }
20 
21     int rob_first_max = this.robFlatRow(rob_first_nums);
22     int rob_no_first_max = this.robFlatRow(rob_no_first_nums);
23 
24     return Math.max(rob_first_max, rob_no_first_max);
25 }
26 
27 public int robFlatRow(int[] num) {
28     if (num == null || num.length == 0) {
29         return 0;
30     }
31 
32     int n = num.length;
33     int[] lookup = new int[n + 1]; // DP array size normally larger than 1
34     lookup[0] = 0;
35     lookup[1] = num[0];
36 
37     for (int i = 2; i <= n; i++) {
38         lookup[i] = Math.max(lookup[i - 1], lookup[i - 2] + num[i - 1]);
39     }
40 
41     return lookup[n];
42 }

Time Complexity: O(N), N is the array size Space Complexity: O(N) since we use extra arrays

References

• House Robber I problem solution
• Leetcode discussion solution