算法随想Day41【动态规划】| LC198-打家劫舍、LC213-打家劫舍Ⅱ、LC337-打家劫舍Ⅲ

标签：LC198 nums max first second 打家劫舍 随想 dp size

LC198. 打家劫舍

自己写的版本，用pair<不取本次的最大收获， 取本次的最大收获>进行记录

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

Carl哥版本

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];
}

LC213. 打家劫舍Ⅱ

想到之前“分糖果”的左右规则，要从两个维度去考虑。

所以就想下，第一次遍历，只考虑从第一个元素到倒数第二个元素（第一个元素可能被选，也可能不被选，但最后一个元素一定不被选）。那为了避免最后一个元素一定不被选的情况，只考虑从第二个元素到最后一个元素。

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

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

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

    return maxRob;
}

LC337. 打家劫舍Ⅲ

pair<int, int> robLoop(TreeNode* root)
{
    if (root == nullptr)
    {
        return {0, 0};
    }
    pair<int, int> left = robLoop(root->left);
    pair<int, int> right = robLoop(root->right);
    //pair<int, int> temp = {left.first + right.first, left.second + right.second};
    pair<int, int> temp = {left.first + right.first, 
        max(left.second + right.second, max(left.first + right.second, left.second + right.first))};

    return {max(temp.first, temp.second), temp.first + root->val};
}
int rob(TreeNode* root)
{
    pair<int, int> result = robLoop(root);
    return max(result.first, result.second);
}

标签：LC198,nums,max,first,second,打家劫舍,随想,dp,size
From： https://www.cnblogs.com/Mingzijiang/p/17218191.html