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

Constraints:

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

题目翻译：
你是一名专业的强盗，计划沿着一条街抢劫房子。每个房子里都藏有一定数量的钱，阻止你抢劫每个房子的唯一约束是相邻的房子有连接的安全系统，如果同一晚上两个相邻的房子被闯入，它将自动联系警察。

给定一个整数数组 nums，表示每个房子的金钱数量，请返回今晚可以在不报警的情况下抢劫的最大金额。

示例 1：

输入：nums = [1,2,3,1]
输出：4
解释：抢劫房子 1 (金钱 = 1) 然后抢劫房子 3 (金钱 = 3)。
你可以抢劫的总金额 = 1 + 3 = 4。
示例 2：

输入：nums = [2,7,9,3,1]
输出：12
解释：抢劫房子 1 (金钱 = 2)，抢劫房子 3 (金钱 = 9) 和抢劫房子 5 (金钱 = 1)。
你可以抢劫的总金额 = 2 + 9 + 1 = 12。

约束条件：

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

public class Solution {
    // 使用动态规划解决问题
    public int rob(int[] nums) {
        // 处理特殊情况
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        
        // 初始化动态规划数组
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        
        // 动态规划过程
        for (int i = 2; i < nums.length; i++) {
            // 每间房子的最大金额为：当前房子的金额加上前前间房子的最大金额 与 前一间房子的最大金额 的较大值
            dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
        }
        
        // 返回最后一个房子的最大金额
        return dp[nums.length - 1];
    }
}

这段代码逐行用中文注释解释如下：

public class Solution {：定义一个名为 Solution 的类。
public int rob(int[] nums) {：定义一个名为 rob 的公共方法，输入参数为一个整数数组 nums，返回值为整数。
if (nums == null || nums.length == 0) {：如果输入数组为空或者长度为 0，处理

best answer:

class Solution {
    public int rob(int[] nums) {
        // 初始化 prev1，表示当前房子的前一间房子的最大金额
        int prev1 = nums[0];
        // 初始化 prev2，表示当前房子的前两间房子的最大金额
        int prev2 = 0;

        // 遍历数组，从第二间房子开始
        for (int i = 1; i < nums.length; i++) {
            // 表示当前房子被抢时的金额
            int rob = nums[i];
            // 如果当前房子不是第二间，那么将前两间房子的最大金额加到当前房子被抢时的金额上
            if (i > 1) rob = rob + prev2;
            // 表示当前房子不被抢时的金额，即前一间房子的最大金额
            int notRob = 0 + prev1;

            // 计算当前房子被抢和不被抢时的最大金额
            int max = Math.max(notRob, rob);
            // 将 prev1 赋值给 prev2，即将前一间房子的最大金额赋值给前两间房子的最大金额
            prev2 = prev1;
            // 将 max 赋值给 prev1，即将当前房子的最大金额赋值给前一间房子的最大金额
            prev1 = max;
        }

        // 返回最后一间房子的最大金额
        return prev1;
    }
}