House Robber Problem C easy to understand Sol

Jyothi
2 min readApr 3, 2022

My first basic sol where no confusion needed and just easy to understand :)
condition is: adjacent houses cannot be robbed
Solution: So s0 can be first house, s1 can be second house,

  • s2 to (first+3rd) houses
  • In a loop starting from 4th house, (where this 4th house can be added to s0 and s1 as not adjacent)
  • Keep adding the current element to s0 and current element to s1
    compare the sums and assign to s,
  • Keep assigning the max value from s
  • Keep moving s0 to s1, s1 to s2, s2 to s..
/* adjacent houses cannot be robbed 
so s0 can be first house, s1 can be second house,
s2 to (first+3rd) houses

in a loop starting from 4th house,
keep adding the current element to s0 and current element to s1
compare the sums and assign to s,
Keep assigning the max value from s
Keep moving s0 to s1, s1 to s2, s2 to s..
*/
int rob(int* nums, int ns){
int ii, mx=0, s0, s1, s2,s;

if (!ns) return 0;
if (ns == 1) return nums[0];
s0 = nums[0];
s1 = nums[1];
if (ns == 2) return (s0 > s1 ? s0 : s1);
s2 = nums[0] + nums[2];
mx = (s2 > s1) ? s2 : s1;
for (ii=3; ii<ns; ii++){
if ((s1 +nums[ii]) > (s0 + nums[ii]))
s = s1 + nums[ii];
else
s = s0 + nums[ii];
if (mx < s) mx = s;
s0=s1; s1=s2; s2 =s;
}
return mx;
}

Next optimized solution, where tried to some temp variables, additions.. :

/* this solution is to reduce the temp. variables
, one extra addition and one extra assignment
s2 can be reduced,
s1 + nums[ii] and s0 + nums[ii] this comparison will take place
when s0 is moved to s1 in next step.
So we can directly initialize s0 to 0, s1 to first house
in loop compare s0+current house with s1 and keep assigning max to s
Keep updating max with max value of s
Keep moving s1 to s0, s to s1
*/
int rob(int* nums, int ns){
int ii, mx=0, s0, s1, s;

if (!ns) return 0;
if (ns == 1) return nums[0];
s0 = 0;
s1 = nums[0];
for (ii=1; ii<ns; ii++){
if (s1 > (s0 + nums[ii]))
s = s1;
else
s = s0 + nums[ii];
if (mx < s) mx = s;
s0=s1; s1=s;
}
return mx;
}

--

--