Try   HackMD

LC 213. House Robber II

tags: leedcode python c++ medium DP

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 a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night .

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police .

Example 1:

Input: nums = [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: nums = [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.

Example 3:

Input: nums = [1,2,3]
Output: 3

Constraints:

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

Solution 1 - DP

Python

class Solution: def rob(self, nums: List[int]) -> int: def calMax(a): if len(a) <= 2: return max(a) n = len(a) dp = [0] * n dp[0] = a[0] dp[1] = max(a[0], a[1]) for i in range(2, n): dp[i] = max(dp[i - 2] + a[i], dp[i - 1]) return dp[-1] if len(nums) <= 1: return max(nums) return max(calMax(nums[1:]), calMax(nums[:-1]))

C++

class Solution { public: int calMaxProfit(vector<int>& nums, int start, int end) { if (end - start + 1 <= 2) { return *max_element(nums.begin() + start, nums.begin() + end + 1); } vector<int> dp(nums.size(), 0); dp[start] = nums[start]; dp[start + 1] = max(nums[start], nums[start + 1]); for (int i = start + 2; i <= end; i++) { dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]); } return dp[end]; } int rob(vector<int>& nums) { if (nums.size() <= 2) { return *max_element(nums.begin(), nums.end()); } int max1 = calMaxProfit(nums, 0, nums.size() - 2); int max2 = calMaxProfit(nums, 1, nums.size() - 1); return max(max1, max2); } };
class Solution { public: int calMaxProfit(vector<int>& nums, int left, int right) { if (left > right) { return 0; } int n = nums.size(); vector<int> cache(n, -1); function<int(int)> dfs = [&](int i) { if (i < left) { return 0; } if (cache[i] != -1) { return cache[i]; } cache[i] = max(dfs(i - 2) + nums[i], dfs(i - 1)); return cache[i]; }; return dfs(right); } int rob(vector<int>& nums) { int n = nums.size(); int a = nums[0] + calMaxProfit(nums, 2, n - 2); int b = calMaxProfit(nums, 1, n - 1); return max(a, b); } };

Solution 2 - DP

C++

class Solution { public: int calMaxProfit(vector<int>& nums, int left, int right) { int f0 = 0; int f1 = 0; for (int i = left; i <= right; i++) { int f2 = max(f0 + nums[i], f1); f0 = f1; f1 = f2; } return f1; } int rob(vector<int>& nums) { int n = nums.size(); int a = nums[0] + calMaxProfit(nums, 2, n - 2); int b = calMaxProfit(nums, 1, n - 1); return max(a, b); } };

Complexity

n = nums.length

Time Complexity Space Complexity
Solution 1 O(n) O(n)
Solution 1 O(n) O(1)

Note

sol1:
既然是排成一圈, 那就選一間房子為頭或是尾巴, 選第0間房子最方便