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

动态规划：从记忆化搜索到递推打家劫舍

news 来源：原创 2024/9/20 0:46:16

LeetCode198 打家劫舍

1、递归搜索+保存计算结果=记忆化搜索

2、1:1翻译成递推

3、空间优化

LeetCode213 打家劫舍II

LeetCode198 打家劫舍

1、递归搜索+保存计算结果=记忆化搜索

回溯三问：

（1）当前操作？枚举第i个房子选/不选

（2）子问题？从前i个房子中的得到的最大金额和

（2）下一个子问题? 分类讨论：

不选：从前i-1个房子中得到的最大金额和

选：从前i-2个房子中得到的最大金额和+nums[i]

记忆化搜索：把递归的计算结果保留下来，下次递归到同样的入参时，就直接返回先前保存的结果。

/** @lc app=leetcode.cn id=198 lang=cpp** [198] 打家劫舍*/// @lc code=start
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;class Solution {
public:int rob(vector<int>& nums) {int n=nums.size();vector<int> cache(n,-1);auto dfs=[&](auto&& dfs,int i)->int{if(i<0) return 0;if(cache[i]!=-1) return cache[i]; return cache[i]=max(dfs(dfs,i-1),dfs(dfs,i-2)+nums[i]);};return dfs(dfs,n-1);}
};

时间复杂度：O(n)

空间复杂度：O(n)

2、1:1翻译成递推

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

时间复杂度：O(n)

空间复杂度：O(n)

3、空间优化

class Solution {
public:int rob(vector<int>& nums) {int f0=0,f1=0;for(int x:nums){int new_f=max(f1,f0+x);f0=f1;f1=new_f;}return f1;}
};

时间复杂度：O(n)

空间复杂度：O(1)

LeetCode213 打家劫舍II

分类讨论，考虑是否偷 nums[0]：

如果偷 nums[0]，那么 nums[1] 和 nums[n−1] 不能偷，问题变成从 nums[2] 到 nums[n−2] 的非环形版本，调用 198 题的代码解决；
如果不偷 nums[0]，那么问题变成从 nums[1] 到 nums[n−1] 的非环形版本，同样调用 198 题的代码解决。

/** @lc app=leetcode.cn id=213 lang=cpp** [213] 打家劫舍 II*/// @lc code=start
#include <iostream>
#include <vector>
using namespace std;class Solution {
public:int rob1(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();return max(nums[0] + rob1(nums, 2, n - 1), rob1(nums, 1, n));}    
};