购物网站代码模板,祖庙网站开发,如何做网站挂qq,深圳市住房和建设局伍家有关于此题我的往期文章,动规五部曲详解篇#xff1a;
leetCode 213. 打家劫舍 II 动态规划 房间连成环怎么偷呢#xff1f;_呵呵哒(#xffe3;▽#xffe3;)的博客-CSDN博客https://heheda.blog.csdn.net/article/details/133409962213. 打家劫舍 II - 力扣#x…关于此题我的往期文章,动规五部曲详解篇
leetCode 213. 打家劫舍 II 动态规划 房间连成环怎么偷呢_呵呵哒(▽)的博客-CSDN博客https://heheda.blog.csdn.net/article/details/133409962213. 打家劫舍 II - 力扣LeetCode 你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额 左闭右闭
1回溯 198. 打家劫舍 - 力扣LeetCode
class Solution {
public:int rob(vectorint nums) {int n nums.size();functionint(int)dfs [](int i) - int {if(i0) return 0;return max(dfs(i-1),dfs(i-2)nums[i]);};return dfs(n-1);}
};
超时
2递归搜索 保存计算结果 记忆化搜索
class Solution {
public:// 记忆化递归int rob(vectorint nums) {int n nums.size();vectorint memo(n,-1);functionint(int)dfs [](int i) - int {if(i0) return 0;int res memo[i];if(res ! -1) return res;return resmax(dfs(i-1),dfs(i-2)nums[i]);};return dfs(n-1);}
};
把 198.打家劫舍 的函数改成 robRange
class Solution {
public:int robRange(vectorint nums,int start,int end) {// int nend-start1;// vectorint memo(n1,-1);vectorint memo(end1,-1);functionint(int)dfs [](int i) - int {if(istart) return 0;int res memo[i];if(res ! -1) return res;return resmax(dfs(i-1),dfs(i-2)nums[i]);};return dfs(end);}int rob(vectorint 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);}
};
31:1 翻译成递推
① 1:1 翻译成递推
class Solution {
public:// 1:1 翻译成递推f[i] max(f[i-1],f[i-2]nums[i]);int rob(vectorint nums) {int n nums.size();vectorint 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 i2;in;i) f[i] max(f[i-1],f[i-2]nums[i]);return f[n-1];}
};
把 198.打家劫舍 的函数改成 robRange
class Solution {
public:int robRange(vectorint nums,int start,int end) {if(end start) return nums[start];// int n nums.size();int n end1;vectorint f(n,0);f[start]nums[start];f[start1]max(nums[start],nums[start1]);for(int istart2;iend;i) f[i] max(f[i-1],f[i-2]nums[i]);return f[end];}int rob(vectorint 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 翻译成递推
class Solution {
public:// 1:1 翻译成递推f[i2] max(f[i1],f[i]nums[i]);int rob(vectorint nums) {int n nums.size();vectorint f(n2,0);for(int i0;in;i) f[i2] max(f[i1],f[i]nums[i]);return f[n1];}
};
把 198.打家劫舍 的函数改成 robRange
class Solution {
public:/*int robRange(vectorint nums,int start,int end) {if(end start) return nums[start];int n nums.size();vectorint f(n2,0);for(int istart;in;i) f[i2] max(f[i1],f[i]nums[i]);return f[end2];}*/int robRange(vectorint nums,int start,int end) {// int n nums.size();int nend1;vectorint f(n2,0);for(int istart;iend;i) f[i2] max(f[i1],f[i]nums[i]);return f[end2];}int rob(vectorint 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优化空间复杂度 class Solution {
public:// 空间优化int rob(vectorint nums) {int n nums.size();if(n0) return 0;if(n1) return nums[0];int f0nums[0];int f1max(nums[0],nums[1]);for(int i2;in;i) {int new_f max(f1,f0nums[i]);f0f1;f1new_f;}return f1;}
};
把 198.打家劫舍 的函数改成 robRange
class Solution {
public:int robRange(vectorint nums,int start,int end) {if(end start) return nums[start];int f0nums[start];int f1max(nums[start],nums[start1]);for(int istart2;iend;i) {int new_f max(f1,f0nums[i]);f0f1;f1new_f;}return f1;}int rob(vectorint 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);}
}; class Solution {
public: // 空间优化int rob(vectorint nums) {int n nums.size();int f00,f10;for(const int x:nums) {int new_f max(f1, f0 x);f0 f1;f1 new_f;}return f1;}
};
class Solution {
public:int robRange(vectorint nums,int start,int end) {int f00,f10;for(int istart;iend;i) {int new_fmax(f1,f0nums[i]);f0f1;f1new_f;}return f1;}int rob(vectorint 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?spm1001.2014.3001.5501leetCode 198.打家劫舍 动态规划 优化空间复杂度_呵呵哒(▽)的博客-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/133390944?spm1001.2014.3001.5501
