DAY52：动态规划（打家劫舍系列）

Leetcode: 198 打家劫舍

基本思路

1、dp下标

dp[i]表示下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

2、递推公式

如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i]。

如果不偷第i房间，那么dp[i] = dp[i - 1]。

所以dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

3、初始化

dp[0]为num[0]，dp[1]为max(num[0],num[1])

时间复杂度: 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(), 0);
        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];
    }
};

Leetcode: 213 打家劫舍II

与上题不同点在于，这个地方所有的房屋都围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。唯一差别在于环的出现。

可以分为两种情况

1、考虑首元素，不考虑尾元素

2、考虑尾元素，不考虑首元素

因此只需要这两种情况都考虑，选一个最大的就可以。

可以写成统一的函数。也可以写两遍。

时间复杂度: 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];
        int result1 = findresult(nums, 0, nums.size() - 2);//考虑首
        int result2 = findresult(nums, 1, nums.size() - 1);//考虑尾
        return max(result1, result2);
    }
    
    int findresult(vector<int>& nums , int start, int end){
        if(start == end) return nums[start];
        vector<int> dp(nums.size(),0);
        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];//返回结果
    }
};

Leetcode: 337 打家劫舍III

与上两题不同，是因为这道题房屋是按照二叉树来进行排列的，因此涉及到树的遍历问题。

树形dp

因为动态规划函数需要通过数据进行计算，所以需要后序遍历，按照左右中的顺序来。

代码随想录

基本思路

1、确定递归函数的参数和返回值

这里我们要求一个节点 偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。

所以dp数组[0]存储不偷该节点的最大金钱，[1]存储偷该节点的最大金钱。

2、确定终止条件

在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回{0,0}

3、遍历顺序

后序遍历

4、递归逻辑

如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0];

如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);

时间复杂度：O(n)

空间复杂度：O(log n)

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[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);//右
        //dp状态转移公式,中
        // 偷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};
     }
};