[刷题防痴呆] 0198 - 打家劫舍 (House Robbe

题目地址

https://leetcode.com/problems/house-robber/

题目描述

198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

 

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

思路

• 求极值想到dp.
• 序列dp. 一维数组. 这里为了方便初始化, 需要使用dummy来构建dp[0].
• state: dp[i]表示抢劫到第i个房子中偷到的最大值
• function: dp[i] = max(dp[i-1], dp[i-2] + A[i-1])
• initialize: dp[0] = 0. dp[1] = A[0]. 这里dp[0] 为dummy构建, 表示前0个没有最大值.
• answer: dp[n]. 表示前n个房子中偷到的最大值.
• 注意, 这里由于每一次向前推进的时候都只与前两个状态有关, 因此可用滚动数组(running array)来优化空间.
• 滚动数组优化方法为: 先写出普通AC, 再通过%的方法来优化. 这里因为只用保留前2个状态, 因此%2即可.

关键点

代码

• 语言支持：Java

## 题目地址
https://leetcode.com/problems/house-robber/

## 题目描述

198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

## 思路
- 求极值想到dp.
- 序列dp. 一维数组. 这里为了方便初始化, 需要使用dummy来构建dp[0].
- state: dp[i]表示抢劫到第i个房子中偷到的最大值
- function: dp[i] = max(dp[i-1], dp[i-2] + A[i-1])
- initialize: dp[0] = 0. dp[1] = A[0]. 这里dp[0] 为dummy构建, 表示前0个没有最大值.
- answer: dp[n]. 表示前n个房子中偷到的最大值.
- 注意, 这里由于每一次向前推进的时候都只与前两个状态有关, 因此可用滚动数组(running array)来优化空间.
- 滚动数组优化方法为: 先写出普通AC, 再通过%的方法来优化. 这里因为只用保留前2个状态, 因此%2即可.

## 关键点



## 代码
* 语言支持：Java

```java
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int n = nums.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        
        return dp[n];
    }
}

// 滚动数组优化
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int n = nums.length;
        int[] dp = new int[2];
        dp[0] = 0;
        dp[1] = nums[0];
        
        for (int i = 2; i <= n; i++) {
            dp[i % 2] = Math.max(dp[(i - 1) % 2], dp[(i - 2) % 2] + nums[i - 1]);
        }
        
        return dp[n % 2];
    }
}