代码随想录Day48——198.打家劫舍 213.打家劫舍II 337.打家劫舍III

198.打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你?不触动警报装置的情况下?，一夜之内能够偷窃到的最高金额。

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

213.打家劫舍II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都?围成一圈?，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警?。

给定一个代表每个房屋存放金额的非负整数数组，计算你?在不触动警报装置的情况下?，今晚能够偷窃到的最高金额。

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

337.打家劫舍III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为?root?。

除了?root?之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果?两个直接相连的房子在同一天晚上被打劫?，房屋将自动报警。

给定二叉树的?root?。返回?在不触动警报的情况下?，小偷能够盗取的最高金额?。

详见：代码随想录 (programmercarl.com)