学习资料:代码随想录
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]);
- }
- };
复制代码 这题挺难
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。 |