自学内容网 自学内容网

代码随想录第四十八天 | 198.打家劫舍, 213.打家劫舍II,337.打家劫舍III

198.打家劫舍

看完想法:这里的偷/不偷,和背包问题中的放/不放感觉是一个道理,所以在dp递推公式中仍旧使用max(dp[i-2] + nums[i], dp[i-1])

int rob(vector<int>& nums) {
    vector<int> dp(nums.size()+1,0);
    if(nums.size()==0) return 0;
    if(nums.size()==1) return nums[0];
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    //0和1的情况要单独用if列出,所以这里起始点是i=2
    for(int i = 2; i<nums.size(); i++){
        dp[i] = max(dp[i-2] + nums[i], dp[i-1]);
    }
    return dp[nums.size()-1];

    }

213.打家劫舍II

看完想法:考虑首尾元素不能同时选的情况,我们分只选首元素和尾元素的情况,这两种情况都算一个dp,然后取最大值就可以。为什么dp不为nums.size() + 1呢?因为dp定义是考虑i之内的房屋,不必要使用

int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        int dp1 = robRange(nums, 0, nums.size() - 2);//只考虑首部元素的情况
        int dp2 = robRange(nums, 1, nums.size() - 1);//只考虑首部元素的情况
        int result = max(dp1, dp2);
        return result;

    }

    //不要囿于实际dp数组的思路,这里是写函数,参数用形参
    int robRange(vector<int>& nums, int start, int end){
        vector<int> dp(nums.size());
        if(start == end) return nums[start];
        //记得初始化
        dp[start] = nums[start];
        dp[start + 1] = max(nums[start], nums[start + 1]);
        for(int i = start+2; i<=end; i++){
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp[end];
    }

337.打家劫舍III

看完想法:对于树的话,首先就要想到遍历方式,前中后序(深度优先搜索)还是层序遍历(广度优先搜索)不记得快去复习一下知识点。解题从递归树的递归三部曲来解题。因为题目中考虑了偷或者不偷两种结果,那最终程序输出取什么呢?当然是取最大的啦,和递归顺序中取偷/不偷的逻辑是一样的。最近面试被问到了时间复杂度,做题的时候还是要分析一下。


class Solution {
public:
    vector<int> robTree(TreeNode* cur){
        //确定终止条件
        if(cur == nullptr) return vector<int>{0,0};
        //递归顺序
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        // 偷cur,那么就不能偷左右节点,所以是left[0] + right[0]
        int val1 = cur->val + left[0] + right[0];
        // 不偷cur,那么可以偷也可以不偷左右节点,则取left/right中偷不偷较大的情况
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }

    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);

    }


原文地址:https://blog.csdn.net/magnetotell/article/details/140218811

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!