Problem: 198. 打家劫舍
思路
👨🏫 参考地址
复杂度
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( n ) O(n) O(n)文章来源：https://www.toymoban.com/news/detail-803507.html
💖 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 ) O(1) O(1)文章来源地址https://www.toymoban.com/news/detail-803507.html
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;
}
到了这里，关于力扣hot100 打家劫舍 DP 滚动数组的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
