博客

打家劫舍系列

198. 打家劫舍

【中等】

思路：动态规划

动态规划五部曲：

1. 确定dp数组以及下标含义

   dp[i]：考虑下标i以内的房屋，最多可以偷窃的金额为dp[i]

2. 确定递推公式

   决定dp[i]的因素就是第i间房间偷还是不偷

   偷：
   
dp[i] = dp[i - 2] + nums[i];


   不偷：
   
dp[i] = dp[i - 1];


   得出：
   
dp[i] = max(dp[i-2] + nums[i], dp[i-1]);


3. 初始化

   
dp[0] = nums[0];


   
dp[1] = max(nums[0], nums[1]);


4. 确定遍历顺序

   从前到后

5. 举例推导dp数组
   
   

• [x]

时间复杂度：O(n)

空间复杂度：O(n)

class Solution {
public:
	int rob(vector<int>& nums) {
		if (nums.size() == 0)  return 0;
		if (nums.size() == 1)  return nums[0];

		vector<int> dp(nums.size());  
		dp[0] = nums[0];
		dp[1] = max(nums[0], nums[1]);
		for (int i = 2; i < nums.size(); i++) {
			dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
		}
		return dp[nums.size() - 1];
	}
};

优化：容器多余；可以用三个常量空间代替

时间复杂度：O(n)

空间复杂度：O(1)

class Solution {
public:
	int rob(vector<int>& nums) {
		if (nums.empty())       return 0;
		if (nums.size() == 1)   return nums[0];
		int size = nums.size();

		int first = nums[0];
		int second = max(nums[0], nums[1]);
		for (int i = 2; i < size; i++) {
			int temp = second;
			second = max(first + nums[i], second);
			first = temp;
		}
		return second;
	}
};

213. 打家劫舍 II

【中等】

题目意思：房子成环

可以分成三种情况考虑：

1. 不包含首尾元素
   
   

2. 包含首元素，不包含尾元素
   
   

3. 包含尾元素，不包含首元素
   
   

第2,3种情况考虑到了第一种，所以不需要第一种

class Solution {
public:
    // 198.打家劫舍的逻辑
    int robRange(const vector<int>& nums, int start, int end) {
        if (end == start) return nums[start];
        vector<int> dp(nums.size());
        dp[start] = nums[start];
        dp[start + 1] = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[end];
    }
    
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        int result1 = robRange(nums, 0, nums.size() - 2); // 情况二
        int result2 = robRange(nums, 1, nums.size() - 1); // 情况三
        return max(result1, result2);
    }    

337. 打家劫舍 III

【中等】

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }
    
    // 长度为2的数组，0：不偷，1：偷
    vector<int> robTree(TreeNode* cur) {
        if (cur == NULL) return vector<int>{0, 0};
        
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        
        // 偷cur
        int val1 = cur->val + left[0] + right[0];
        // 不偷cur
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
};

股票系列