算法刷题记录 Day41

算法刷题记录 Day41

Date: 2024.04.08

lc 337. 打家劫舍III

struct Money{
    int take_cur;
    int not_take_cur;
};

class Solution {
public:
    // 每个节点需要返回偷了的最大值，和没偷的最大值。
    Money traverse(TreeNode* root, Money cur_money){
        Money res;
        res.take_cur = 0;
        res.not_take_cur = 0;
        if(root == nullptr) return res;

        Money left = traverse(root->left, cur_money);
        Money right = traverse(root->right, cur_money);

        // 两种选择，一种是取当前节点，则其子节点必不能取；另一种是不取当前节点，则其子节点选取或不取的更大值；
        res.take_cur = root->val + left.not_take_cur + right.not_take_cur;
        res.not_take_cur = max(left.take_cur, left.not_take_cur) + max(right.take_cur, right.not_take_cur);
        return res;
        
    }


    int rob(TreeNode* root) {
        if(root == nullptr) return 0;

        // 遍历方式：后序遍历(自底向上)；
        Money tmp;
        tmp.take_cur = 0;
        tmp.not_take_cur = 0;
        Money res = traverse(root, tmp);
        return max(res.take_cur, res.not_take_cur);
    }
};

lc 213. 打家劫舍II

class Solution {
public:
    // 思路1:分别计算包含第一个和包含最后一个的值，取两者更大的值；
    int takeMoney(vector<int>& nums, int startIdx, int endIdx){
        int n = endIdx - startIdx + 1;
        if(n == 1)  return nums[startIdx];
        vector<int> dp(n, 0);
        dp[0] = nums[startIdx];
        dp[1] = max(nums[startIdx], nums[startIdx+1]);

        for(int i=2; i<n; i++){
            dp[i] = max(dp[i-1], dp[i-2]+nums[startIdx+i]);
        }
        return dp[n-1];

    }

    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 1)  return nums[0];
        vector<int> dp(n, 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        int res1 = takeMoney(nums, 0, n-2);
        int res2 = takeMoney(nums, 1, n-1);
        return max(res1, res2);
    }
};

lc 198. 打家劫舍

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 1)  return nums[0];
        // 我们需要确定要不要取当前的房间内的金币。取的代价是左右都不能再取。
        // dp[i]表示从前i个房间偷盗后，能获得的最高的金额;
        vector<int> dp(n, 0);
        // 最多跳两个，不可能跳三个；
        // 1.前一个没取，取当前的；2.前一个取了，当前的跳过；3.前一个没取，当前的跳过；
        // dp[i] = max(dp[i-2]+nums[i], dp[i-1])；
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        for(int i=2; i<n; i++){
            dp[i] = max(dp[i-2], max(dp[i-2]+nums[i], dp[i-1]));
        }
        return dp[n-1];

    }
};