)
动态规划取舍问题开辟f[n]数组保存当前偷窃前n个房屋的最大金额。1. 最后状态f[n]的值可以对nums[n]取或者不取2. 转移方程为f[n] max( f[n-1], f[n-2] nums[n]) // 不取取 , n23. 初始条件f[0] nums[0],f[1] max(nums[0], nums[1])class Solution { public int rob(int[] nums) { int len nums.length; if(len 0) return 0; if(len 1) return nums[0]; if(len 2) return Math.max(nums[0],nums[1]); int[] f new int[len]; f[0] nums[0]; f[1] Math.max(nums[0],nums[1]); for(int i 2; ilen; i){ f[i] Math.max(f[i-1], f[i-2] nums[i]); } return f[len-1]; } }因为只用到前2个状态的值可以简化代码为class Solution { public int rob(int[] nums) { int len nums.length; if(len 0) return 0; if(len 1) return nums[0]; int f0 nums[0]; int f1 Math.max(nums[0],nums[1]); for(int i 2; ilen; i){ int f2 Math.max(f1, f0 nums[i]); f0 f1; f1 f2; } return f1; } }
