笔记:代码随想录算法练习营day39:LeetCode 198.打家劫舍,213.打家劫舍II,33
学习资料:代码随想录198.打家劫舍
力扣题目链接
思路：有点像贪婪，是一个不断比力取最大路径的思路
界说：偷到下标为i的这家，能偷到的最大值
递推公式：选当前这家偷能得到的钱和不偷当前这家的钱作比力，选能偷到的最大金额。因为这个金额是逐一递推过来的，所以是能够代表最大值的。
初始化：把第一家和第二家初始化，简朴来说，因为递推公式须要i-1和i-2
遍历次序：顺着偷
打印：
// 五部曲
// 定义:dp为偷到第i家时,偷到的最高金额
// 递推:投当下这家和偷前一家的对比
// 初始化:第一家处为第一家的金额,第二家处为偷第一家和第二家中最多的那一家
// 遍历顺序:从一开始一家一家偷
class Solution {
public:
int rob(vector<int>& nums) {
vector<int> dp(nums.size(),0);
if(nums.size()==1) return nums;
dp = nums;
dp = max(nums,nums);
for(int i =2;i<nums.size();i++){
dp = max(nums+dp,dp);
//cout<<dp;
}
return dp;
}
};
213.打家劫舍II
力扣题目链接
思路：把上一题的函数打包了，然后把给定命组拆出一个不含第一个数的数组，拆出一个不含第二个数的数组，末了两个一比力
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size()==1) return nums;
int result1 = toubushiqiang(nums,0,nums.size()-2);
int result2 = toubushiqiang(nums,1,nums.size()-1);
return max(result1,result2);
}
private:
int toubushiqiang(vector<int>& nums,int start,int end){
if(end==start) return nums;
vector<int> dp(nums.size());
dp = nums;
dp = max(nums,nums);
for(int i=start+2;i<=end;i++){
dp = max(nums+dp,dp);
}
return dp;
}
};
337.打家劫舍 III
力扣题目链接
思路：
界说：不用dp数组了，按递归来，递归函数界说为该节点偷或不偷两种状态劳绩的金额
终止条件：遇空返回
遍历次序：从树的底层往上推导到根节点，后序
单层递归逻辑：还是偷与不偷该节点的比力
// 每个节点返回长度为2的两个数组,表示选或不选该节点所得到的金钱
// 终止条件:遇到空节点,返回,偷不偷空节点金额都是0
// 遍历顺序:后序
// 递推公式:递推要得到/返回两个偷或不偷的结果
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
vector<int> toubushiqiang(TreeNode* cur){
if(cur==nullptr) return vector<int>{0,0};
vector<int> leftval = toubushiqiang(cur->left);
vector<int> rightval = toubushiqiang(cur->right);
int val1 = cur->val+leftval+rightval; //选该节点1
int val2 = max(leftval,leftval)+max(rightval,rightval); //不选该节点0
return{val2,val1};
}
public:
int rob(TreeNode* root) {
vector<int> result = toubushiqiang(root);
return max(result,result);
}
}; 这题挺难
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]