F.动态规划-入门DP-打家劫舍：198. 打家劫舍

题目链接198. 打家劫舍中等LCR 089. 打家劫舍中等算法原理此题与下题完全相同动态规划算法-简单多状态dp问题11.按摩师解法动态规划0ms击败100.00%时间复杂度O(N)空间复杂度O(N)①状态表示dp0[i]不选择第 i -1 个房屋获得的最大价值dp1[i]选择第 i -1个房屋获得的最大金额②状态转移方程遍历到当前房屋 i 时有两种选择选或不选选前一个房屋必须不选dp1[i] dp0[i-1] nums[i]不选前一个房屋可选可不选dp0[i] Math.max(dp1[i-1], dp0[i-1])0③初始化dp0[0] 0不选第1个房屋dp1[0] nums[0]选第1个房屋④填表顺序从左往右⑤返回值返回最后一个房屋选或不选这两种状态下的最大值max(dp0[n-1],dp1[n-1])滚动数组空间优化0ms击败100.00%时间复杂度O(N)空间复杂度O(1)由于遍历到当前房屋时更新仅依靠前一个房屋的状态的选或不选因此可用单个变量代替整个数组实现“滚动数组”将空间复杂度压倒O(1)遍历到当前房屋前dp0不偷上一个房子时的最大金额dp1偷上一个房子的最大金额遍历到当前房屋时新状态max(这个偷上个不偷这个不偷上个随便)这个偷上个不偷xdp0这个不偷上个随便0上个随便偷和不偷的最大值max(dp1,dp0)因此dpmax(dp0x,0dp1,dp0)max(dp0x,dp1)更新逻辑下一轮遍历的 “上一个房子”就是我们现在处理的 “当前房子 x”因此下一轮的 dp0不偷上一个房子 → 对应现在的 “不偷当前房子 x” 的最大金额也就是“保持偷上一个房子的最大金额而当前房子不偷”而这个值就是我们现在的 dp1因此dp0dp1下一轮的 dp1偷上一个房子 → 对应现在的 “偷到当前房子 x” 的最大金额也就是我们刚算出来的 dpJava代码class Solution { public int rob(int[] nums) { int nnums.length; //dp0[i]不选第i-1个房屋的最大价值 int[] dp0new int[n]; dp0[0]0; //dp1[i]选第i-1个房屋的最大价值 int[] dp1new int[n]; dp1[0]nums[0]; for(int i1;in;i){ //选前一个必须不选 dp1[i]dp0[i-1]nums[i]; //不选前一个可选可不选 dp0[i]Math.max(dp1[i-1],dp0[i-1])0; } return Math.max(dp0[n-1],dp1[n-1]); } }class Solution { //滚动数组空间优化 public int rob(int[] nums) { int nnums.length; int dp00,dp10; for(int x:nums){ int dpMath.max(dp0x,dp1); dp0dp1; dp1dp; } return dp1; } }