力扣hot100 打家劫舍 DP 滚动数组

Problem: 198. 打家劫舍

思路

👨?🏫 参考地址

复杂度

时间复杂度: $O(n)$

空间复杂度: $O(n)$

💖 Code

class Solution {
	public static int rob(int[] nums)
	{
		int n = nums.length;
		if (n == 1)
			return nums[0];
		int[] f = new int[n + 1];//f[i] 表示在前 i 间房屋里能偷窃到的 最大 金额
//		初始化
		f[0] = 0;//偷 0 家金额为 0
		f[1] = nums[0];
//		状态转移
		for (int i = 2; i <= n; i++)
//							 偷当前家                      不偷当前家
			f[i] = Math.max(f[i - 2] + nums[i-1], f[i - 1]);
		return f[n];
	}
}

💖 DP空间优化版

空间复杂度：$O(1)$

public int rob(int[] nums) {
    int prev = 0;
    int curr = 0;

    // 每次循环，计算“偷到当前房子为止的最大金额”
    for (int i : nums) {
        // 循环开始时，curr 表示 dp[k-1]，prev 表示 dp[k-2]
        // dp[k] = max{ dp[k-1], dp[k-2] + i }
        int temp = Math.max(curr, prev + i);
        prev = curr;
        curr = temp;
        // 循环结束时，curr 表示 dp[k]，prev 表示 dp[k-1]
    }

    return curr;
}