当前位置: 首页 > news >正文

leetCode 213. 打家劫舍 II + 动态规划 + 从记忆化搜索到递推 + 空间优化

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

leetCode 213. 打家劫舍 II 动态规划 房间连成环怎么偷呢?_呵呵哒( ̄▽ ̄)"的博客-CSDN博客icon-default.png?t=N7T8https://heheda.blog.csdn.net/article/details/133409962213. 打家劫舍 II - 力扣(LeetCode)


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

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



>>左闭右闭

(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 翻译成递推:f[i] = max(f[i-1],f[i-2]+nums[i]);
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 翻译成递推:f[i+2] = max(f[i+1],f[i]+nums[i]);
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)优化空间复杂度

  • f[i] = max(f[i-1],f[i-2]+nums[i]);
  • newF = max(f1,f0+nums[i]);
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);}
};
  • f[i+2] = max(f[i+1],f[i]+nums[i]);
  • newF = max(f1,f0+nums[i]);
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博客icon-default.png?t=N7T8https://heheda.blog.csdn.net/article/details/133409962leetCode 198.打家劫舍 动态规划入门:从记忆化搜索到递推-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/weixin_41987016/article/details/134179583?spm=1001.2014.3001.5501leetCode 198.打家劫舍 动态规划 + 优化空间复杂度_呵呵哒( ̄▽ ̄)"的博客-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/weixin_41987016/article/details/133390944?spm=1001.2014.3001.5501

http://www.lryc.cn/news/218140.html

相关文章:

  • 网络编程套接字(二)
  • [极客大挑战 2019]Knife 1(两种解法)
  • 国家统计局教育部各级各类学历教育学生情况数据爬取
  • mysql、clickhouse时间日期加法
  • 21.合并两个有序链表
  • thinkphp漏洞复现
  • 暴力递归转动态规划(十三)
  • java EE 进阶
  • 记录paddlepaddle-gpu安装
  • django如何连接sqlite数据库?
  • 面试算法47:二叉树剪枝
  • 云安全-云原生k8s攻击点(8080,6443,10250未授权攻击点)
  • 性能压力测试主要目标及步骤
  • VLAN与配置
  • API接口安全设计
  • 服务器的管理口和业务口
  • 【gpt redis】原理篇
  • python二次开发Solidworks:排雷以及如何排雷?
  • 广告引擎检索技术快速学习
  • Scala的类和对象
  • SQL中 <>(不等于)运算符只会匹配那些具有非空值的记录
  • 冒泡排序(Java)
  • k8s集群调度
  • Scala中类的继承、抽象类和特质
  • 小程序如何实现登录数据持久化
  • Maven本地配置获取nexus私服的依赖
  • 第02章-变量与运算符
  • SpringBoot数据响应、分层解耦、三层架构
  • go测试库之apitest
  • K8S删除资源后一直处于Terminating状态无法删除解决方法