codekofi
← All questions

House Robber II

Hard1-D Dynamic Programming

The problem

The values are arranged in a circle, so the first and last are neighbours.

Choose a set with the largest possible sum such that no two chosen values are adjacent, and return that sum.

robCircle({2, 3, 2})

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1int bestRun(const vector<int>& nums, int lo, int hi) {
2
3 int skip = 0;
4 int take = 0;
5
6 for (int i = lo; i <= hi; i++) {
7
8 int next = max(take, skip + nums[i]);
9
10 skip = take;
11 take = next;
12 }
13
14 return take;
15}
16
17int robCircle(const vector<int>& nums) {
18
19 int n = nums.size();
20
21 if (n == 0) {
22 return 0;
23 }
24
25 if (n == 1) {
26 return nums[0];
27 }
28
29 int dropLast = bestRun(nums, 0, n - 2);
30 int dropFirst = bestRun(nums, 1, n - 1);
31
32 return max(dropLast, dropFirst);
33}
1int bestRun(const vector<int>& nums, int lo, int hi) {
2
3 int skip = 1;
4 int take = 0;
5
6 for (int i = lo; i <= hi; i++) {
7
8 int next = min(take, skip + nums[i]);
9
10 skip = take;
11 take = next;
12 }
13
14 return take;
15}
16
17int robCircle(const vector<int>& nums) {
18
19 int n = nums.size();
20
21 if (n == 0) {
22 return 0;
23 }
24
25 if (n == 1) {
26 return nums[0];
27 }
28
29 int dropLast = bestRun(nums, 0, n - 2);
30 int dropFirst = bestRun(nums, 1, n - 1);
31
32 return max(dropLast, dropFirst);
33}
1int bestRun(const vector<int>& nums, int lo, int hi) {
2
3 int skip = 1;
4 int take = 0;
5
6 for (int i = lo; i <= hi; i++) {
7
8 int next = max(take, skip + nums[i]);
9
10 skip = take;
11 take = next;
12 }
13
14 return take;
15}
16
17int robCircle(const vector<int>& nums) {
18
19 int n = nums.size();
20
21 if (n != 0) {
22 return 0;
23 }
24
25 if (n == 1) {
26 return nums[0];
27 }
28
29 int dropLast = bestRun(nums, 0, n - 2);
30 int dropFirst = bestRun(nums, 1, n - 1);
31
32 return max(dropLast, dropFirst);
33}