一、思路

动态规划：

1. 确定属性：$dp[i]dp[i]$表示从数组下标为$00$的房间开始到达数组下标为$ii$的房间此时所能获得的最多的偷窃金额。
2. 确定边界条件： $dp[0]=nums[0]dp[0]\; =\; nums[0]$
3. 确定状态转移方程： $dp[i]=max(dp[i-2]+nums[i],dp[i-1])dp[i]\; =\; max(dp[i\; -\; 2]\; +\; nums[i],\; dp[i\; -\; 1])$
4. 确定结果值：假定$nn$为$numsnums$数组的长度，$dp[n-1]dp[n\; -\; 1]$即为从数组下标为$00$的房间开始到达数组下标为$n-1n\; -1$的房间此时所能获得的最多的偷窃金额。也就是题目要求的，因此我们最后返回$dp[n-1]dp[n\; -\; 1]$即可。

二、代码

初步代码

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int rob (int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[n - 1];
    }
}

此时时间复杂度是$O(n)O(n)$，空间复杂度是$O(n)O(n)$

优化后的代码

我们可以发现$dp[i]dp[i]$只跟之前两次的状态有关，因此我们可以不用创建$O(n)O(n)$空间的复杂度，可以用滚动数组代替，优化空间复杂度为$O(1)O(1)$

$JavaJava$代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int rob (int[] nums) {
        // write code here
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int a = nums[0];
        int b = Math.max(nums[0], nums[1]);
        int sum = 0;
        for (int i = 2; i < n; i++) {
            int tmp = b;
            b = Math.max(a + nums[i], b);
            a = tmp;
        }
        return b;
    }
}

$CC$++代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int rob(vector<int>& nums) {
        // write code here
        int n = nums.size();
        if (n == 1) {
            return nums[0];
        }
        int a = nums[0];
        int b = max(nums[0], nums[1]);
        for (int i = 2 ; i < n; i++) {
            int tmp = b;
            b = max(nums[i] + a, b);
            a = tmp;
        }
        return b;
    }
};

$python3python3$ 代码

class Solution:
    def rob(self , nums: List[int]) -> int:
        # write code here
        n = len(nums)
        if n == 1:
            return nums[0]
        a = nums[0]
        b = max(nums[0], nums[1])
        for i in range(2, n):
            tmp = b
            b = max(nums[i] + a, b)
            a = tmp
        return b;