One Method to Solve All House Robber Problems on LeetCode

Today, we'll discuss the "House Robber" series of problems (known as House Robber in English). This series is representative and technique-oriented in dynamic programming.

The House Robber series consists of three problems, designed with increasing difficulty. The first problem is a standard dynamic programming issue, the second incorporates a circular array condition, and the third uniquely combines bottom-up and top-down dynamic programming approaches with binary trees, which I find very enlightening.

Let's start our analysis with the first problem.

House Robber I

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

There is a row of houses on the street, represented by an array nums of non-negative integers. Each element nums[i] represents the amount of cash in the i-th house. You are a professional thief who wants to rob as much cash as possible from these houses. However, adjacent houses cannot be robbed simultaneously, or the alarm will be triggered, and you'll be in trouble.

Please 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.