198. 打家劫舍
动态规划
初始
class Solution { public: int rob(vector<int> &nums) { int n = nums.size(); vector<int> dp(n + 1); if (n == 1) { return nums[0]; } if (n == 2) { return max(nums[0], nums[1]); } dp[1] = nums[0]; dp[2] = max(nums[0], nums[1]); for (int i = 3; i <= n; i++) { dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1]); } return dp[n]; } };
dp[i]表示前i间房子可以偷取的财物的最大值。首先剔除一间房屋和两间房屋的情况。一件房屋时就偷取这间。两间房屋时偷取其中金额较大的一间。当房屋数大于2时，设房间数为k，有2种选择：
1.偷第k间房屋，那么就不能偷第k-1间，所以总金额为偷取前k-2间房屋最高金额加上偷第k间房屋金额之和。
2.不偷第k间房屋，则总金额为偷取前k-1间房屋的最高金额。
在这2个选项中选择数额较大的，即为偷窃前k间房屋能偷窃的最高总金额。
状态转移方程：
dp[i]=max(dp[i−2]+nums[i−1],dp[i−1])
边界条件：
dp[1]=nums[0]
dp[2]=max(nums[0],nums[1])
优化(滚动数组)
class Solution { public: int rob(vector<int> &nums) { int n = nums.size(); if (n == 1) { return nums[0]; } if (n == 2) { return max(nums[0], nums[1]); } int p = nums[0]; int q = max(nums[0], nums[1]); int cur; for (int i = 2; i < n; i++) { cur = max(p + nums[i], q); p = q; q = cur; } return cur; } };
考虑到每间房屋最高总金额只与该房屋前两间的最高总金额有关，所以使用滚动数组,每一时刻只用存放前两间房屋的最高总金额。空间复杂度O(1)。
