CODEWITHSUNDEEP
c++dynamic-programming
user8305079
user8305079

Reputation:

Intuition behind the base cases of this DP

I am trying to solve the following DP question:

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. You cannot rob adjacent houses since doing that would alert the police.

One of the solutions given is:

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty())
            return 0;

        if(nums.size()==1)
            return nums[0];

        vector<int> dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        for(int i=2; i<(int)nums.size(); i++) {
            dp[i] = max(dp[i-2]+nums[i], dp[i-1]);
        }

        return dp[nums.size()-1];
    }
};

Could someone please point out the intuition behind initialization of dp[1] as:

dp[1] = max(nums[0], nums[1]);

I initialized it as dp[1] = nums[1]. However, it then breaks on test cases like [3,1,4,10]. When we initialize it as max(nums[0], nums[1]);, aren't we sort of changing the input array to [3,3,4,10]? How does it help us reach the final (correct) solution?

Note: Question is from here.

Edit: Do the guidelines recommend taking into account our main DP formula while hard-coding the base cases for questions like these?

Upvotes: 2

Views: 66

Answers (1)

Polb
Polb

Reputation: 700

To maximize the amount of money you can rob, you must start robbing either from the first house or the second. You cannot rob them both, since they are adjacent and this would not respect the given condition.

You cannot rob none of them since you would miss one house and it would result into a value that is not a global maximum.

That initialization can be seen as "The maximum amount you can rob starting from house 0 and going to house 1 (inclusive)". Your initialization says that the maximum you can rob from the first two houses is only 1 (not 3, as it must be), which is false, resulting into a false maximum.

Upvotes: 1

Related Questions