企业官网建设流程全解析

动态规划：

取舍问题

开辟f[n]数组，保存当前偷窃前n个房屋的最大金额。

1. 最后状态，f[n]的值，可以对nums[n]取或者不取

2. 转移方程为：f[n] = max( f[n-1], f[n-2] + nums[n]) // 不取，取 , n>=2

3. 初始条件：

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; i<len; 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; i<len; i++){ int f2 = Math.max(f1, f0 + nums[i]); f0 = f1; f1 = f2; } return f1; } }