代码随想录day48 | DS18B20温度传感器工作原理详解

198.打家劫舍 213.打家劫舍II

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        int result = robRange(nums,0, nums.size() -2);
        int result1 = robRange(nums,1, nums.size()-1);
        return max(result,result1);
    }
    int robRange(vector<int>& nums, int start, int end) {
    if(start == end) return nums[start];
    vector<int> dp(nums.size());
    dp[start] = nums[start];
    dp[start+1] = max(nums[start+1],nums[start]);
        for (int i = start+2; i <=end ; ++i) {
            dp[i] = max(dp[i-2]+nums[i], dp[i-1]);
        }
        return dp[end];
}
};

● 337.打家劫舍III
还要消化

class Solution {
public:
    unordered_map<TreeNode*, int> umap;
    int rob(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root ->right == NULL) return root->val;
        if (umap[root]) return umap[root];

        int val1 = root->val;
        if (root->left) val1+= rob(root->left->left) + rob(root->left->right);
        if (root->right) val1+= rob(root->right->left) + rob(root->right->right);

        int val2 = rob(root->left) + rob(root->right);
        umap[root] = max(val1,val2);
        return max(val1, val2);
    }
};