House Robber 2 Leetcode problem giving incorrect output
I am solving the Leetcode problem House Robber II. The problem says,
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. The constraint is you can not rob two adjacent houses. Also, the houses in that place are arranged in a circle, so the first and last houses are also adjacent.
Here is the link: https://leetcode.com/problems/house-robber-ii/
I have used the top-down approach to solve it. This is function definition: dp(index, isFirstHouseRobbed)
In the function body, I am checking if(index === nums.length - 1 && isFirstHouseRobbed === true) return 0;
. Here is the complete function:
var rob = function(nums) {
const dp = (index, isFirstHouseRobbed) => {
if (index >= nums.length) {
return 0;
}
if (index === nums.length - 1 && isFirstHouseRobbed === true) {
return 0;
}
if (index === 0) {
// Two choice: rob or not rob
// rob
let max1 = dp(index + 2, true) + nums[index];
// not rob
let max2 = dp(index + 1, false);
return Math.max(max1, max2);
} else {
// Two choice: rob or not rob
// rob
let max1 = dp(index + 2, false) + nums[index]; // This does not work
// --->(line 20) let max1 = dp(index + 2, isFirstHouseRobbed) + nums[index]; // But this works.
// not rob
let max2 = dp(index + 1, false); // This does not work
// --->(line23) let max2 = dp(index + 1, isFirstHouseRobbed); // But This works.
return Math.max(max1, max2);
}
}
return dp(0, false);
};
This solution works only if I use line20 and line23. The only difference between those two lines and their previous lines is I am using the variable isFirstHouseRobbed
instead of passing false
. My question is, in the main function call I am calling dp(0, false)
. So, the value of isFirstHouseRobbed
should be set to false
. My question is, why using false
instead of isFirstHouseRobbed
not working, where the value of isFirstHouseRobbed
is set to false
anyway. Maybe I am missing something easy, but could not figure it out. Any help would be greatly appreciated.
Solution 1:
It's not always false
; one of your recursive cases passes true
for the second parameter. This makes sense — there wouldn't be much point in having it be a parameter if it never changed.