One Method to Solve All House Robber Problems on LeetCode

Today, we will discuss the "House Robber" series of problems, which are representative and skillful dynamic programming problems.

The House Robber series consists of three problems, with a well-designed difficulty progression. The first problem is a standard dynamic programming problem, the second introduces the condition of a circular array, and the third one is more advanced, combining bottom-up and top-down dynamic programming approaches with binary trees, which I find very insightful.

Let's start with the first problem.

House Robber I

LeetCode problem 198 "House Robber" is described as follows:

There is a row of houses, each represented by a non-negative integer in an array nums, where each element nums[i] represents the amount of cash in the i-th house. Now, you are a professional robber, and you aim to steal as much cash as possible from these houses. However, adjacent houses cannot be robbed on the same night as it will trigger the alarm, and you'll get caught.

Write an algorithm to calculate the maximum amount of cash you can rob without triggering the alarm. The function signature is as follows:

int rob(int[] nums);

int rob(vector<int>& nums);

def rob(nums: List[int]) -> int:

func rob(nums []int) int

var rob = function(nums) {}

For example, given the input nums=[2,1,7,9,3,1], the algorithm returns 12. The thief can rob houses at nums[0], nums[3], nums[5], obtaining a total of 2 + 9 + 1 = 12, which is the optimal choice.

The problem is easy to understand and clearly exhibits the characteristics of dynamic programming. In our previous article Dynamic Programming Explained, we summarized that solving dynamic programming problems involves finding the 'states' and 'choices', and that's all there is to it.