House Robber: dynamic programming with just two numbers | Python

House Robber is LeetCode problem 198, and the greedy answer (rob the richest house first) is wrong. This video builds the dynamic programming solution from scratch: the brute-force call tree drawn from its real trace (the same question asked again and again), the one rule that replaces it (skip the house, or rob it and add the answer from two houses back), and the two-number loop that runs in O(n) time and O(1) memory. Then the real Python code runs step by step: every state on screen comes from executing the solution on our example. Plus the tempting every-other-house shortcut running and failing, and the other problems that use the same take-or-skip idea. Problem: LeetCode 198, House Robber (Medium) · https://leetcode.com/problems/house-r... Pattern: 1-D Dynamic Programming · On: NeetCode 150, Blind 75, Grind 169, LeetCode Top Interview 150, LeetCode 75 Chapters 0:00 Cold open 0:26 The problem 1:01 The obvious answer 1:47 The trick 2:38 Dry run 3:46 The code 4:17 Cost and traps 5:01 The pattern The Python solution from the video def rob(houses): prev, best = 0, 0 for cash in houses: take = prev + cash prev = best best = max(best, take) return best Cost: O(n) time, O(1) extra memory. Sources • LeetCode 198: House Robber: https://leetcode.com/problems/house-r... • NeetCode: House Robber, written solution (recursion, memoisation, then two variables): https://neetcode.io/solutions/house-r... • LeetCode 213: House Robber II: https://leetcode.com/problems/house-r... • LeetCode 337: House Robber III: https://leetcode.com/problems/house-r... • LeetCode 70: Climbing Stairs: https://leetcode.com/problems/climbin... • LeetCode 740: Delete and Earn: https://leetcode.com/problems/delete-... • NeetCode 150: https://neetcode.io/practice • Blind 75: https://neetcode.io/practice • Grind 169: https://www.techinterviewhandbook.org... • LeetCode Top Interview 150: https://leetcode.com/studyplan/top-in... • LeetCode 75: https://leetcode.com/studyplan/leetco... The problem is explained in our own words with our own example. Every state in the animation comes from running the solution shown, and the code is tested (plus a random cross-check against the brute force) before the video is made. #LeetCode #HouseRobber #CodingInterview #DSA #Python