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 家金额为 0f[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;
}