day-48 代码随想录算法训练营（19） 动态规划 part 09

198.打家劫舍

思路：

• 1.dp存储：偷到第i家时，偷到的最大金额
• 2.dp[i]=max(dp[i-1],dp[i-2]+numa[i])
• 3.初始化：dp[0]=nums[0]  dp[1]=max(nums[0],nums[1])
• 4.遍历顺序：2-n

213.打家劫舍II

分析：考虑两种情况：不考虑偷第一家、不考虑偷最后一家

思路：

• 1.dp存储：偷到第i家时，偷到的最大金额
• 2.dp[i]=max(dp[i-1],dp[i-2]+nums[i])
• 3.初始化：分情况初始化
• 4.遍历顺序：1.0~n-1   2.1~n

337.打家劫舍III

分析：

• 递归+动态规划

思路：

• 后序遍历，每个节点都有两个状态，偷或者不偷
• 偷的时候，子节点都不能偷；不偷的时候，左右节点考虑偷

class Solution {
public:
    int rob(TreeNode* root) {
       vector<int>res=judge(root);
       return res[0]>res[1]?res[0]:res[1];
    }
 
    vector<int> judge(TreeNode*root){
        if(root==nullptr) return {0,0};
 
        vector<int>left=judge(root->left);
        vector<int>right=judge(root->right);
 
        int valYes=root->val+left[0]+right[0];//偷当前节点
        int valNo=max(left[0],left[1])+max(right[0],right[1]);
        return {valNo,valYes};
    }
 
    
};

121.买卖股票的最佳时机

思路一：贪心

• 遍历数组，每次取最小值，并且每次都用当前值-最小值，更新最大差值

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //分析：只有卖出>买入才有利润,只能买一次
        int res=0,minNum=INT_MAX;
        for(auto it:prices){
            minNum=min(it,minNum);
            res=max(it-minNum,res);
        }
        return res;
    }
};

思路二：

1.dp存储：

2.dp

3.初始化：

4.遍历顺序：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>> dp(n,vector(2));
        dp[0][0]-=prices[0];//持有
        dp[0][1]=0;//不持有
        for(int i=1;i<n;i++){
            dp[i][0]=max(dp[i-1][0],-prices[i]);//当前持有（之前买的和当前买的取最大值）
            dp[i][1]=max(dp[i-1][1],prices[i]+dp[i-1][0]);//当前不持有（之前就不持有和今天不持有）
        }
        return dp[n-1][1];
    }
};

122.买卖股票的最佳时机||

思路一：贪心

• 只要有利润就直接进行买卖

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res=0;
        for(int i=1;isize();i++){
            if(prices[i]>prices[i-1]) res+=prices[i]-prices[i-1];
        }
        return res;
        
    }
};

思路二：动态规划