How to solve the problem of robbing houses in leetcode

Editor to share with you how to solve the problem of home robbery in leetcode, I believe that most people do not know much about it, so share this article for your reference, I hope you will learn a lot after reading this article, let's learn about it!

Topic link

Https://leetcode-cn.com/problems/house-robber/

Topic description

You are a professional thief who plans to steal houses along the street. There is a certain amount of cash hidden in every room, and the only constraint to your theft is that the adjacent houses are equipped with an interconnected anti-theft system. If two adjacent houses are broken into by thieves on the same night, the system will automatically alarm.

Given an array of non-negative integers representing the deposit amount of each house, calculate the maximum amount you can steal without touching the alarm device.

Example 1:

Input: [1, 2, 2, 3, 1]

Output: 4

Explanation: steal House No. 1 (amount = 1), and then steal House No. 3 (amount = 3).

The maximum amount stolen is 1 + 3 = 4.

Example 2:

Input: [2, 7, 9, 3, 1]

Output: 12

Explanation: steal House 1 (amount = 2), House 3 (amount = 9), and then House 5 (amount = 1).

The maximum amount stolen is 2 + 9 + 1 = 12.

The idea of solving the problem

Tags: dynamic plannin

Dynamic programming equation: DP [n] = MAX (dp [n-1], dp [n-2] + num)

Because you can't break into an adjacent house, the maximum value that can be stolen from a house in the current location is either the maximum value that can be stolen by a house, or the maximum value that can be stolen by a house with the value of the current house, and the maximum value between the two.

For example, if the maximum value of theft in room 1 is 3, that is, dp [1] = 3, the maximum value of theft in room 2 is 4, that is, dp [2] = 4, the value of room 3 itself is 2, that is num=2, then dp [3] = MAX (dp [2], dp [1] + num) = MAX (4Ling 3 + 2) = 5jue 3 can steal a maximum of 5.

Time complexity: O (n), n is the length of the array

Code

Java version

Class Solution {

Public int rob (int [] nums) {

Int len = nums.length

If (len = = 0)

Return 0

Int [] dp = new int [len + 1]

Dp [0] = 0

Dp [1] = nums [0]

For (int I = 2; I