Leetcode September Day14

Problem -

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

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

Example =
"""
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
"""
Intuition - One approach could be to be greedy i.e. pick the max out of three rob it , move on and again pick the max out of the other 3 possibilities.

However, we can miss some cases here, as we don't know what values lie in future.
Consider following scenario - [2,4,8,40]
If we are greedy we will pick 8. But if we pick 4 we would be able to pick 40 as well and result will be 44.
So, greedy won't work here. We need to enumerate all possibilities/states. So, we will do that. And we will use memoization to reduce the Time Complexity. And because we are using memoization, we term it as a dp solution.
Solution -

class Solution:
    def rob(self, nums: List[int]) -> int:
        cache = {}
        def dp(idx):
            if idx < 0:
                return 0
            else:
                res = cache.get(idx, None)
                if res is not None:
                    return res
                else:
                    res = max(dp(idx-1), dp(idx-2) + nums[idx])
                    cache[idx] = res
                    return res
        return dp(len(nums)-1)

Comments

[Merzaq]

The genius to transmit well must imperatively explain in a clear way the idea of ​​his algorithm.
other sites offer algorithms with explanation of the paradigm to benefit those interested.