https://leetcode.com/problems/house-robber/?embedable=true Description: 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 systems connected and . it will automatically contact the police if two adjacent houses were broken into on the same night Given an integer array representing the amount of money of each house, return . nums the maximum amount of money you can rob tonight without alerting the police Example 1: 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. Example 2: Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12. Solution: Oh my God, that is Dynamic programming. I can’t believe that I’ve solved a dynamic programming problem. Looks like we cannot use a greedy approach because, for example in array [3 5 3] result should be six instead of five. That is why we need another algorithm. I must have  spent much time on this problem, but nope. In dynamic programming, you must always find the base function. In our case Largest amount that you can rob from the first house to nth indexed house. f(n) = Amount of money at the ith index house. Ai = At each house, we have the choice of robbing it or leaving it. In the first case: if we pick the last house: then, we can’t pick (n-1)th house, hence f(n)= An + f(n-2) In the second case: if we leave last house: then, we will stick with the max profit till (n-1)th house, hence f(n)= f(n-1) Let us see base cases. n = 0, clearly f(0) = A0. n = 1, then f(1) = max(A0, A1). Hence we can summarize the formula as following : f(n)= max( An + f(n-2) , f(n-1) ) You may have thought that we need smth else, hah me too, but that is it. I must have thought that dynamic problems have an insane level. After this one, I don’t think so. Let’s code it: public int rob(int[] nums) {
    if (nums == null){
        return 0;
    }
    if (nums.length == 1){
        return nums[0];
    }
    int[] rob = new int[nums.length];
    rob[0] = nums[0];
    rob[1] = Math.max(nums[0], nums[1]);

    for (int i = 2; i < nums.length; i++){
        int curAndPrev = nums[i] + rob[i-2];
        rob[i] = Math.max(curAndPrev, rob[i-1]);
    }
    return rob[rob.length-1];
} Write comments and share your reactions. Peace.

2021 - HackerNoon Contributor of the Year - INNOVATION

2022 - HackerNoon Contributor of the Year - Design

2022 - HackerNoon Contributor of the Year - Software Architecture

2021 - HackerNoon Contributor of the Year - COMPUTER-SCIENCE

2021 - Rick Sanchez of the Year

Nominated for 2022 - HackerNoon Contributor of the Year - Design

Nominated for 2022 - HackerNoon Contributor of the Year - Software Architecture

Too Long; Didn't Read

Get free API security automated scan in minutes

House Robber

Too Long; Didn't Read

@deft

RELATED STORIES