每天一道LeetCode----從數組中選擇若幹不連續元素使得總和最大

House Robber

原題連結House Robber

給定一個數組，選取一些元素使得總和最大，選取規則為

• 不能連續取兩個元素，即選取的元素之間至少要間隔一個其它元素

每個元素都有選與不選兩種可能，使得用動态規劃求解，令dp[n]表示nums[0 : n)的選取結果

代碼如下

class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int> dp(nums.size() + , );
        for(int i = ; i < dp.size(); ++i)
            dp[i] = std::max(nums[i - ] + dp[i - ], dp[i - ]);
        return dp[nums.size() + ];
    }
};
           

觀察發現實際上dp數組隻用到了dp[i-2]和dp[i-1]，是以可以優化空間複雜度

class Solution {
public:
    int rob(vector<int>& nums) {
        int pprev = , prev = , cur = ;
        for(int i = ; i < nums.size(); ++i)
        {
            cur = std::max(nums[i] + pprev, prev);
            pprev = prev;
            prev =  cur;
        }
        return cur;
    }
};
           

House Robber II

原題連結House Robber II

意思是給定的數組是循環的，第一個挨着最後一個。要求和上面一樣

這種情況下就不能用上面的方法了，因為如果同時選擇了第一個和最後一個，就不符合要求。是以需要單獨分開計算，分兩種情況（n是給定數組元素個數）

• 選擇第一個，此時最後的結果相當于nums[0] + max_sum(nums[2 : n - 2])
• 不選擇第一個，此時最後的結果為max_sum(nums[1 : n - 1])

代碼如下

class Solution {
public:
    int rob(vector<int>& nums) {
        return (nums.empty())
                    ? 
                    : std::max(nums[] + max_sum(nums, , nums.size() - ), max_sum(nums, , nums.size()));
    }
private:
    int max_sum(vector<int>& nums, int first, int last)
    {
        int pprev = , prev = , cur = ;
        for(int i = first; i < last; ++i)
        {
            cur = std::max(nums[i] + pprev, prev);
            pprev = prev;
            prev = cur;
        }
        return cur;
    }
};
           

House Robber III

原題連結House Robber III

要求和上面一樣，但這回是二叉樹，相連的父子節點不能同時選擇

周遊一遍二叉樹即可（不考慮重複情況下，複雜度較高）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) {
        return max_sum(root, false);
    }
private:
    int max_sum(TreeNode* root, bool robbed)
    {
        if(!root)   return ;
        if(robbed)
            return max_sum(root->left, false) + max_sum(root->right, false);
        else
            return std::max(root->val + max_sum(root->left, true) + max_sum(root->right, true),
                            max_sum(root->left, false) + max_sum(root->right, false));
    }
};
           

由于在max_sum函數的else語句塊中需要重複周遊兩次root->left和root->right，會造成複雜度很高，解決辦法是記錄下已經計算過的節點

周遊一遍二叉樹，通過unordered_map記錄已計算過的節點（考慮重複情況，複雜度較低）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) {
        return max_sum(root, false);
    }

private:
    int max_sum(TreeNode* root, bool robbed)
    {
        if(!root)   return ;
        if(robbed)
            return max_sum(root->left, false) + max_sum(root->right, false);
        else
            return map_.find(root) != map_.end()
                        ? map_[root]
                        : map_[root] = std::max(root->val + max_sum(root->left, true) + max_sum(root->right, true),
                                                max_sum(root->left, false) + max_sum(root->right, false));
    }
private:
    unordered_map<TreeNode*, int> map_;
};