This is the 8th day of my participation in the August More Text Challenge. For details, see:August is more challenging

The title

You are a professional thief, planning to steal houses along the street. Each house has a certain amount of cash hidden in it, and the only restriction that affects your theft is that the adjacent houses are connected to the anti-theft system. If two adjacent houses are broken into on the same night, the system will automatically alarm.

Given an array of non-negative integers representing the amount of money stored in each house, calculate the maximum amount you can steal in one night without activating the alarm.

The sample

Input: [1,2,3,1] Output: 4 Explanation: Steal house 1 (amount = 1), then steal house 3 (amount = 3). Maximum amount stolen = 1 + 3 = 4. Input: [2,7,9,3,1] Output: 12 Explanation: Steal house 1 (amount = 2), steal house 3 (amount = 9), then steal house 5 (amount = 1). Maximum amount stolen = 2 + 9 + 1 = 12.Copy the code

prompt

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

Their thinking

So they’re restricting the two adjacent rooms from stealing consecutively, so let’s make a boundary judgment here

  • When the room numberkLess than or equal to2When:
    • K == 1: directly returns the result
    • K == 2: take the highest value of the two rooms
  • When the number of rooms is greater than2When:

    • If room K is stolen, room K-1 cannot be stolen: the maximum is the total amount of K + (k-2)

    • Do not steal room K: total amount of maximum k – 1

    • State transition: dp [I] = Math. Max (nums [I] + dp [2] I -, dp] [I – 1)

Code implementation

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        // Yes means to steal, no means not to steal
        // Since only the total amount of K-1 and the total amount of K-2 need to be retained, variables are used for optimization
        int yes = nums[0], no = 0, tmp;

        for(int i = 1; i < n; ++i){
            / / equal to dp [I] = math.h Max (nums [I] + dp [2] I -, dp] [I - 1)
            tmp = Math.max(nums[i] + no, yes);
            no = yes;
            yes = tmp;
        }

        returnyes; }}Copy the code

Complexity analysis

  • Time complexity: O(n)O(n)O(n).
  • Space complexity: O(1)O(1)O(1).

The last

The article has the bad place that writes, ask big guy people not stingy give instruction, mistake is most can let a person grow, wish I and big guy the distance between shorten gradually!

If you think the article is helpful to you, please like, collect, follow, comment one key four connect support, your support is my creation biggest power!!

Source: leetcode-cn.com/problems/ho…