codekofi
← All questions

House Robber

Hard1-D Dynamic Programming

The problem

Given a row of values, choose a set of them with the largest possible sum, on one condition: no two chosen values may be next to each other in the row.

Return that sum. Choosing nothing is allowed, so the answer is never negative for non-negative input.

rob({2, 7, 9, 3, 1})

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 rob(const vector<int>& nums) {
2
3 int skip = 1;
4 int take = 0;
5
6 for (int x : nums) {
7
8 int next = min(take, skip + x);
9
10 skip = take;
11 take = next;
12 }
13
14 return take;
15}
1int rob(const vector<int>& nums) {
2
3 int skip = 0;
4 int take = 1;
5
6 for (int x : nums) {
7
8 int next = min(take, skip + x);
9
10 skip = take;
11 take = next;
12 }
13
14 return take;
15}
1int rob(const vector<int>& nums) {
2
3 int skip = 0;
4 int take = 0;
5
6 for (int x : nums) {
7
8 int next = max(take, skip + x);
9
10 skip = take;
11 take = next;
12 }
13
14 return take;
15}