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

打家劫舍 II + 动态规划 + 从记忆化搜索到递推 + 空间优化"/>

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

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

leetCode 213. 打家劫舍 II 动态规划 房间连成环怎么偷呢？_呵呵哒(￣▽￣)"的博客-CSDN博客. 打家劫舍 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 翻译成递推：

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 翻译成递推：

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）优化空间复杂度

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);}
};

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博客 198.打家劫舍 动态规划入门:从记忆化搜索到递推-CSDN博客=1001.2014.3001.5501leetCode 198.打家劫舍 动态规划 + 优化空间复杂度_呵呵哒(￣▽￣)"的博客-CSDN博客=1001.2014.3001.5501