LeetCode 198 打家劫舍
https://leetcode.cn/problems/house-robber/description/
普通递归
对于一维数组，子问题可以分解为 长度更小的问题，如何分解呢？可以从第一个或最后一个开始分解。
对于本问题输入数组长度为 len 是否可以分解为长度为 len-1，len-2，len-3 这种长度小的问题呢？
可以关心最后一个（或第一个），这个打劫 那么调用下层 len -2 ，这个不打那么调用下层 len -1
class Solution {
public:
int robb(vector<int>& nums,int end){
if(end == 0) return nums[0];
if(end==1) return max(nums[0],nums[1]);
return max(robb(nums,end-1),nums[end]+robb(nums,end-2));
}
int rob(vector<int>& nums) {
return robb(nums,nums.size()-1);
}
};
但是输入数组一多就超时了。
记忆化递归
注意到有些 子树 重复了，这些可以记录下来，下次再求值的时候就直接用。
class Solution {
public:
vector<int> res;
int robb(vector<int>& nums,int end){
if(res[end]!=-1) return res[end];
if(end == 0) return nums[0];
if(end==1) return max(nums[0],nums[1]);
res[end] = max(robb(nums,end-1),nums[end]+robb(nums,end-2));
return res[end];
}
int rob(vector<int>& nums) {
res = vector<int>(nums.size(),-1);
return robb(nums,nums.size()-1);
}
};
记忆化递归->动态规划
dfs 就是上面的递归函数。f 数组可以看成递归函数的返回值数组。
class Solution {
public:
int rob(vector<int>& nums) {
vector<int> fun_res(nums.size(),-1);
fun_res[0] = nums[0];
fun_res[1] = max(nums[0],nums[1]);
for(int i =2;i<nums.size();i++){
fun_res[i] = max(fun_res[i-1],fun_res[i-2]+nums[i]);
}
return fun_res[nums.size()-1];
}
};
但是不完美，有些数组只有一个值就会报错，可以处理一下数组下标为负数的情况。
class Solution {
public:
int rob(vector<int>& nums) {
vector<int> fun_res(nums.size(),-1);
fun_res[0] = nums[0];
// fun_res[1] = max(nums[0],nums[1]);
for(int i =1;i<nums.size();i++){
fun_res[i] = max(fun_res[i-1],(i-2>=0?fun_res[i-2]:0)+nums[i]);
}
return fun_res.back();
}
};