笔记:代码随想录算法训练营day39:LeetCode 198.打家劫舍,213.打家劫舍II,337.打家劫舍III

学习资料:代码随想录

198.打家劫舍

力扣题目链接

思路：有点像贪心，是一个不断比较取最大路径的思路

定义：偷到下标为i的这家，能偷到的最大值

递推公式：选当前这家偷能得到的钱和不偷当前这家的钱作比较，选能偷到的最大金额。因为这个金额是逐一递推过来的，所以是能够代表最大值的。

初始化：把第一家和第二家初始化，简单来说，因为递推公式需要i-1和i-2

遍历顺序：顺着偷

打印：

// 五部曲
// 定义:dp[i]为偷到第i家时,偷到的最高金额
// 递推:投当下这家和偷前一家的对比
// 初始化:第一家处为第一家的金额,第二家处为偷第一家和第二家中最多的那一家
// 遍历顺序:从一开始一家一家偷

class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int> dp(nums.size(),0);
        if(nums.size()==1) return nums[0];

        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);

        for(int i =2;i<nums.size();i++){
            dp[i] = max(nums[i]+dp[i-2],dp[i-1]);
            //cout<<dp[i];
        }      

        return dp[nums.size()-1]; 
    }
};

213.打家劫舍II

力扣题目链接

思路：把上一题的函数打包了，然后把给定数组拆出一个不含第一个数的数组，拆出一个不含第二个数的数组，最后两个一比较

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==1) return nums[0];
        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[start];
        
        vector<int> dp(nums.size());

        dp[start] = nums[start];

        dp[start+1] = max(nums[start],nums[start+1]);

        for(int i=start+2;i<=end;i++){
            dp[i] = max(nums[i]+dp[i-2],dp[i-1]);
        }
        return dp[end];
    }
};

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[0]+rightval[0];                             //选该节点1
        int val2 = max(leftval[0],leftval[1])+max(rightval[0],rightval[1]);     //不选该节点0

        return{val2,val1};
    }
public:
    int rob(TreeNode* root) {
        vector<int> result = toubushiqiang(root);
        return max(result[0],result[1]);
    }
};

这题挺难