Leetcode 198: house raiding

You are a professional thief , Plan to steal houses along the street . There is a certain amount of cash in every room , The only restriction on your theft is that adjacent houses are equipped with interconnected anti-theft systems , 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 storage amount of each house , Count you Without triggering the alarm , The maximum amount that can be stolen overnight .

  Ideas ：

Five steps ：

1. determine dp Array （dp table） And the meaning of subscripts

dp[i]： Consider Subscripts i（ Include i） The houses within , The maximum amount that can be stolen is dp[i].

2. Determine the recurrence formula

decision dp[i] The most important factor is i Steal the room or not .

If you steal the first i room , that dp[i] = dp[i - 2] + nums[i] , namely ： The first i-1 The house must not be considered , find Subscript i-2（ Include i-2） The houses within , The maximum amount that can be stolen is dp[i-2] Add the number i The money stolen from the room .

If you don't steal the first i room , that dp[i] = dp[i - 1], Consider i-1 room ,（ Note that this is about , It doesn't have to be stolen i-1 room , This is a confusing point for many students ）

then dp[i] Taking the maximum , namely dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

3. dp How to initialize an array

From the recursive formula dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]); It can be seen that , The basis of the recursive formula is dp[0] and dp[1]

from dp[i] By definition ,dp[0] It must be nums[0],dp[1] Namely nums[0] and nums[1] The maximum value of is ：dp[1] = max(nums[0], nums[1]);

4. Determine the traversal order

dp[i] It's based on dp[i - 2] and dp[i - 1] Derived from , So it must be traversal from front to back ！

5. deduction dp Array

//  Dynamic programming 
class Solution {
	public int rob(int[] nums) {
		if (nums == null || nums.length == 0) return 0;
		if (nums.length == 1) return nums[0];

		int[] dp = new int[nums.length];
		dp[0] = nums[0];
		dp[1] = Math.max(dp[0], nums[1]);
		for (int i = 2; i < nums.length; i++) {
			dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
		}

		return dp[nums.length - 1];
	}
}