神刀安全网

C++ Coding Exercise – House Robber II (Dynamic Programming)

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.

This is an extension ofHouse Robber. Submit your solution at: https://leetcode.com/problems/house-robber-ii/

Dynamic Programming

For the non-circle street, we know that the DP equation is:

F(0) = H(0) F(1) = max(H(0), H(1)) F(n) = max(F(n - 1), F(n - 2) + H(n)) // for n >= 2
F(0) = H(0) F(1) = max(H(0), H(1)) F(n) = max(F(n - 1), F(n - 2) + H(n)) // for n >= 2

if F(n) denotes the maximum profit the thieve gets when he/she walks to House(n). and H(n) denotes the value that he/she can rob at house n .

Now, the street is a circular so House 0 is adjacent with House n-1. But we still can use the DP equation solver however, there are two cases: House(0) is robbed or House(0) is not robbed.

So, we compare the maximum of two cases. Remember that if we rob House(0), we can’t rob House(n-1) so the maximum value is stored at F(n-2).

class Solution { public:     int rob(vector<int>& nums) {         if (nums.size() == 0) {             return 0;         }         if (nums.size() == 1) {             return nums[0];         }         int n = nums.size();         int *f = new int[n];         f[0] = nums[0];         f[1] = max(nums[0], nums[1]);         // House(0) is robbed         for (int i = 2; i < n - 1; i ++) {             f[i] = max(f[i - 1], f[i - 2] + nums[i]);         }         int x = f[n - 2];         // House(0) is not robbed         f[0] = 0;         f[1] = nums[1];         for (int i = 2; i < n; i ++) {             f[i] = max(f[i - 1], f[i - 2] + nums[i]);         }         x = x > f[n - 1] ? x : f[n - 1];         return x;     } };
class Solution { public:     int rob(vector<int>& nums) {         if (nums.size() == 0) {             return 0;         }         if (nums.size() == 1) {             return nums[0];         }         int n = nums.size();         int *f = new int[n];         f[0] = nums[0];         f[1] = max(nums[0], nums[1]);         // House(0) is robbed         for (int i = 2; i < n - 1; i ++) {             f[i] = max(f[i - 1], f[i - 2] + nums[i]);         }         int x = f[n - 2];         // House(0) is not robbed         f[0] = 0;         f[1] = nums[1];         for (int i = 2; i < n; i ++) {             f[i] = max(f[i - 1], f[i - 2] + nums[i]);         }         x = x > f[n - 1] ? x : f[n - 1];         return x;     } };

Two O(n) scans.

–EOF–

GD Star Rating

loading…

420 words

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » C++ Coding Exercise – House Robber II (Dynamic Programming)

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址