Скачать или смотреть 198. House Robber | LeetCode Medium | Python Solution | Array, Dynamic Programming

Leetcode medium problem 198. House Robber, detailed explanation and solution in python language.

LeetCode Problem Link: https://leetcode.com/problems/house-r...
Solution (Python Code): https://github.com/shaheershukur/Leet...

House Robber II:    • 213. House Robber II | LeetCode Medium | P...  
House Robber III:    • 337. House Robber III | LeetCode Medium | ...  

#leetcode #python #solution

Problem Statement:
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 nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
______________________________________________________________

LeetCode problem solving helps in improving one's problem solving and coding skills . Also, it helps in clearing technical interviews at top tech companies like Microsoft, Google, Amazon, Facebook, Walmart, Apple etc.
(FAANGM, MAANGM, Product based companies)

CC of video:
we are given an array of integers representing the amount of money present in the house.
and we need to rob the maximum amount of money such that we do not rob from two adjacent houses.

lets look at some examples.
if there is only 1 house, then we can simply rob whatever amount is present in that house.

if there are two houses, we can only rob 1 house among the two, because, we cannot rob 2 adjacent houses. so we will choose the house with maximum amount of money.

now, if there are 3 houses, to decide whether we need to rob the third house or not, we must look at the previous 2 houses. ie, if the second house has more money than the first and third house combined, then we can rob the second house, else we will rob the first and third houses.

so, if there are 3 or more houses, whats happening is, to decide whether we need to choose the current house or not, we must look at the previous 2 houses. ie, we are dependent on the previous results, or we can say that there is a repeating overlapping subproblem. therfore this problem is a good candidate for dynamic programming.

so now lets look at how to solve this problem when there are 3 or more houses, with an example.
we know that if there is only 1 house, we will rob that house.
now lets consider 2 houses. we will rob the maximum among the two, which is 7 in this case.

now lets consider 3 houses. here if we are robbing the third house, we can also rob the first house, which will give a total money of 16.
if we are not robbing the third house, then the best amount of money we can have till the second house is 7.
since 16 is greater than 7, we will rob the 1st and 3rd houses.

now lets consider the next 3 houses.
here, if we are robbing the 3rd house, then we can include the maximum amount of money we had robbed till the 1st house, which will give a total money of 10.
if we are not robbing the 3rd house, then the best amount of money we can have till the second house is 16.
since 16 is greater than 10, we will rob the 2nd house alone.

now lets consider the next 3 houses.
here, if we are robbing the 3rd house, then we can include the maximum amount of money we had robbed till the 1st house, which will give a total money of 17.
if we are not robbing the 3rd house, then the best amount of money we can have till the second house is 16.
since 17 is greater than 16, we will rob the 1st and 3rd houses.

so, at the end, we have a maximum total money of 17.

now lets code the solution.

we will store the length of the array in this variable.
if there is only 1 element in the array, we dont have to do anything, we can simply return that amount.

to solve this using dynamic programming, we will create a new array of same size, initially filled with zeroes.

we know that, when there is 1 house, we will rob that house.
when there are two houses, we will rob the maximum of the two houses.

now, we will handle 3 houses at once, using a for loop.
here if we are robbing the current house or the third house, then we can also add the total amount we got till the first house.
else we can rob the second house alone.
among these two, we will be choosing the maximum amount.

in the end, we will be returning the total amount of money we got after visiting the last house.