213. 打家劫舍 II-Toy模板网

这篇具有很好参考价值的文章主要介绍了213. 打家劫舍 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

关于此题我的往期文章,动规五部曲详解篇：

leetCode 213. 打家劫舍 II 动态规划房间连成环怎么偷呢？_呵呵哒(￣▽￣)"的博客-CSDN博客https://heheda.blog.csdn.net/article/details/133409962213. 打家劫舍 II - 力扣（LeetCode）

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

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

213. 打家劫舍 II,c++

>>左闭右闭

（1）回溯 198. 打家劫舍 - 力扣（LeetCode）

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

超时！！！

（2）递归搜索 + 保存计算结果 = 记忆化搜索

class Solution {
public:
    // 记忆化递归
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> memo(n,-1);
        function<int(int)>dfs = [&](int i) -> int {
            if(i<0) return 0;
            int& res = memo[i];
            if(res != -1) return res;
            return res=max(dfs(i-1),dfs(i-2)+nums[i]);
        };
        return dfs(n-1);
    }
};

把 198.打家劫舍的函数改成 robRange

class Solution {
public:
    int robRange(vector<int>& nums,int start,int end) {
        // int n=end-start+1;
        // vector<int> memo(n+1,-1);
        vector<int> memo(end+1,-1);
        function<int(int)>dfs = [&](int i) -> int {
            if(i<start) return 0;
            int& res = memo[i];
            if(res != -1) return res;
            return res=max(dfs(i-1),dfs(i-2)+nums[i]);
        };
        return dfs(end);
    }

    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        int result1 = robRange(nums, 0, n - 2); // 情况二
        int result2 = robRange(nums, 1, n - 1); // 情况三
        return max(result1, result2);
    }
};

（3）1:1 翻译成递推

① 1:1 翻译成递推： $213. 打家劫舍 II,c++$

class Solution {
public:
    // 1:1 翻译成递推：f[i] = max(f[i-1],f[i-2]+nums[i]);
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n,0);
        if(nums.size()==0) return 0;
        if(nums.size()==1) return nums[0];
        f[0]=nums[0];
        f[1]=max(nums[0],nums[1]);
        for(int i=2;i<n;i++) 
            f[i] = max(f[i-1],f[i-2]+nums[i]);
        return f[n-1];
    }
};

把 198.打家劫舍的函数改成 robRange

class Solution {
public:
    int robRange(vector<int>& nums,int start,int end) {
        if(end == start) return nums[start];
        // int n = nums.size();
        int n = end+1;
        vector<int> f(n,0);
        f[start]=nums[start];
        f[start+1]=max(nums[start],nums[start+1]);
        for(int i=start+2;i<=end;i++) 
            f[i] = max(f[i-1],f[i-2]+nums[i]);
        return f[end];
    }
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        int result1 = robRange(nums, 0, n - 2); // 情况二
        int result2 = robRange(nums, 1, n - 1); // 情况三
        return max(result1, result2);
    }
};

② 1:1 翻译成递推： $213. 打家劫舍 II,c++$

class Solution {
public:
    // 1:1 翻译成递推：f[i+2] = max(f[i+1],f[i]+nums[i]);
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n+2,0);
        for(int i=0;i<n;i++) 
            f[i+2] = max(f[i+1],f[i]+nums[i]);
        return f[n+1];
    }
};

把 198.打家劫舍的函数改成 robRange

class Solution {
public:
    /*
    int robRange(vector<int>& nums,int start,int end) {
        if(end == start) return nums[start];
        int n = nums.size();
        vector<int> f(n+2,0);
        for(int i=start;i<n;i++)  
            f[i+2] = max(f[i+1],f[i]+nums[i]);
        return f[end+2];
    }*/
    int robRange(vector<int>& nums,int start,int end) {
        // int n = nums.size();
        int n=end+1;
        vector<int> f(n+2,0);
        for(int i=start;i<=end;i++)  
            f[i+2] = max(f[i+1],f[i]+nums[i]);
        return f[end+2];
    }
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        int result1 = robRange(nums, 0, n - 2); // 情况二
        int result2 = robRange(nums, 1, n - 1); // 情况三
        return max(result1, result2);
    }
};

（4）优化空间复杂度

$213. 打家劫舍 II,c++$
$213. 打家劫舍 II,c++$

class Solution {
public:
    // 空间优化
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n==0) return 0;
        if(n==1) return nums[0];
        int f0=nums[0];
        int f1=max(nums[0],nums[1]);
        for(int i=2;i<n;i++) {
            int new_f = max(f1,f0+nums[i]);
            f0=f1;
            f1=new_f;
        }
        return f1;
    }
};

把 198.打家劫舍的函数改成 robRange

class Solution {
public:
    int robRange(vector<int>& nums,int start,int end) {
        if(end == start) return nums[start];
        int f0=nums[start];
        int f1=max(nums[start],nums[start+1]);
        for(int i=start+2;i<=end;i++) {
            int new_f = max(f1,f0+nums[i]);
            f0=f1;
            f1=new_f;
        }
        return f1;
    }

    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        int result1 = robRange(nums, 0, n - 2); // 情况二
        int result2 = robRange(nums, 1, n - 1); // 情况三
        return max(result1, result2);
    }
};

$213. 打家劫舍 II,c++$
$213. 打家劫舍 II,c++$

class Solution {
public: 
    // 空间优化
    int rob(vector<int>& nums) {
        int n = nums.size();
        int f0=0,f1=0;
        for(const int& x:nums) {
            int new_f = max(f1, f0 + x);
            f0 = f1;
            f1 = new_f;
        }
        return f1;
    }
};

class Solution {
public:
    int robRange(vector<int>& nums,int start,int end) {
        int f0=0,f1=0;
        for(int i=start;i<=end;i++) {
            int new_f=max(f1,f0+nums[i]);
            f0=f1;
            f1=new_f;
        }
        return f1;
    }
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        int result1 = robRange(nums, 0, n - 2); // 情况二
        int result2 = robRange(nums, 1, n - 1); // 情况三
        return max(result1, result2);
    }
};

我的往期文章推荐：

leetCode 213. 打家劫舍 II 动态规划房间连成环怎么偷呢？_呵呵哒(￣▽￣)"的博客-CSDN博客https://heheda.blog.csdn.net/article/details/133409962leetCode 198.打家劫舍动态规划入门:从记忆化搜索到递推-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/134179583?spm=1001.2014.3001.5501leetCode 198.打家劫舍动态规划 + 优化空间复杂度_呵呵哒(￣▽￣)"的博客-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/133390944?spm=1001.2014.3001.5501文章来源地址https://www.toymoban.com/news/detail-740277.html

到了这里，关于213. 打家劫舍 II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！