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.

Contains Duplicate and Missing Number

Implement Queue using Stacks

2021 - HackerNoon Contributor of the Year - INNOVATION

2021 - HackerNoon Contributor of the Year - COMPUTER-SCIENCE

House Robber

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

2022 Noonies Nominee Sergei on Programming, Technology, and More

The Noonification: Understanding Dynamic Programming So You Can Use It Effectively (9/4/2023)

A n00b's Guide To Data Structures and Algorithms

A Selfish Mining Double Spending Attack Simulator

All You Need to Know About Dynamic Programming

Dynamic Programming for Brute-Forcers

2022 Noonies Nominee Sergei on Programming, Technology, and More

The Noonification: Understanding Dynamic Programming So You Can Use It Effectively (9/4/2023)

A n00b's Guide To Data Structures and Algorithms

A Selfish Mining Double Spending Attack Simulator

All You Need to Know About Dynamic Programming

Dynamic Programming for Brute-Forcers

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps