JLUVicent

21打家劫舍&213打家劫舍II&337打家劫舍III

 
  • 2023年 04月03日
  • 0 阅读

day48

21.打家劫舍

题目链接：198. 打家劫舍

解题思路：参考 视频

当前状态偷不偷取决于前一个房间和前两个房间有没有被偷

1.确定dp[i]及下标的含义：考虑下标i所能偷的最多金额为dp[i]

2.确定递推公式，分两种情况

偷i:那么i-1一定不能偷，即dp[i-2]+nums[i]

不偷i:dp[i-1]

dp[i] = max( dp[i-1] , dp[i-2]+nums[i]);

3.初始化 \(dp[0] = nums[0] dp[1] = max( nums[0],nums[1])\) 其余都初始化为0

4.确定遍历顺序

从前向后遍历

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

5.打印dp数组

198.打家劫舍

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        // 注意要判断下数组长度为1的情况，数组长度为空也可以判断下 题目限制了
        if( n == 1) return nums[0];  
        vector<int> dp(n,0);
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);

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

213.打家劫舍II

题目链接：213. 打家劫舍 II

解题思路：参考 视频

分三种情况，

image-20230403101308777

因此直接取2，3情况的最大值就可以了。

class Solution {
public:

    int myrob( 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+1],nums[start]);	//初始取两个的最大值
        for( int i = start+2; i <= end; i++){
            dp[i] = max( dp[i-1] ,dp[i-2]+nums[i]);
        }
        return dp[end];
    }

    int rob(vector<int>& nums) {
        int n = nums.size();
        if( n == 1) return nums[0];
        if( n == 2) return max( nums[0],nums[1]);//这个可以没有
        int result1 = myrob( nums,0,n-2);
        int result2 = myrob( nums,1,n-1);
        return max( result1,result2);

    }
};

337.打家劫舍III

题目链接：337. 打家劫舍 III

解题思路：参考 视频

后序遍历

如果抢了当前节点，两个孩子就不能动，如果没抢当前节点，就可以考虑抢左右孩子（注意这里说的是“考虑”）

本题为树形dp的入门题目，在树上进行状态转移，确定长度为2的dp数组来表示当前节点偷与不偷所得到的最大金钱。

递推三部曲融合动规五部曲来进行解释

1.确定递归函数的返回值和参数

vector<int> robTree(treeNode *cur){
   
}

此时返回的数组就是dp数组，dp[0]记录不偷该节点所得到的最大金钱，下标为1表示偷该节点所得到的最大金钱。

2.确定终止条件

if( cur == NULL ) return vector<int>{0,0}; //相当于dp数组初始化

3.确定遍历顺序

后续遍历（左右中）

vector<int> left = robtree(cur->left);
vector<int> right = robtree(cur->right);
//中

4.确定单层递归逻辑

//偷cur
int val1 = cur->val + left[0] + right[0];
//不偷cur
int val2 = max(left[0],left[1]) + max(right[0],right[1]);
return { val2,val1 };

5.举例推导dp数组

img

/**
 * 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 {
public:

    vector<int> robtree( TreeNode* cur){
        // 终止条件
        if( cur == NULL) return{0,0};
        // 后序遍历
        vector<int> left = robtree(cur->left);
        vector<int> right = robtree(cur->right);
        // 偷cur
        int val1 = cur->val + left[0] + right[0];
        // 不偷cur
        int val2 = max(left[0],left[1]) + max(right[0],right[1]);
        return {val2,val1};

    }

    int rob(TreeNode* root) {
        vector<int> result = robtree(root);
        return max(result[1],result[0]);
    }
};
搜索