Dynamic programming problem (VIII)

One 、 raid homes and plunder houses ( One )

solution : Dynamic programming

Some people may think that the use of greed , Just steal the most money from others , Either even or odd number of all the money , But sometimes in order to steal more money , Maybe they will give up two companies without stealing , So this scheme is not feasible , We still consider dynamic programming .

• use dp[i] The length is i Array of , How much money can you steal at most , As long as each transition state is gradually accumulated, you can get the money that the whole array can steal .
• If the array length is 1, Only one family , It must have stolen the family , The most profitable , therefore dp[1]=nums[0]
• Every time for a family , We choose to steal him or not , If we choose to steal, then the previous one must not steal , Therefore, the maximum benefit of the accumulated superior , Similarly, if you choose not to steal him , Then we can accumulate up to one level of income . So the transfer equation is dp[i]=max(dp[i−1],nums[i−1]+dp[i−2]). there i stay dp Array length in , stay nums Middle is the subscript .
  

class Solution {
    
public:
    int rob(vector<int>& nums) {
    
        //dp[i] The length is i Array of , How much money can you steal at most 
        vector<int> dp(nums.size() + 1, 0); 
        // The length is 1 Only the first one can be stolen 
        dp[1] = nums[0]; 
        for(int i = 2; i <= nums.size(); i++)
            // For each family, you can choose to steal or not 
            dp[i] = max(dp[i - 1], nums[i - 1] + dp[i - 2]); 
        return dp[nums.size()];
    }
};

Time complexity ：O(n), among n Is array length , Traversing the array once
Spatial complexity ：O(n), Dynamically plan the space of auxiliary array

Two 、 raid homes and plunder houses ( Two )

solution : Dynamic programming

• Using the original scheme is ： use dp[i] The length is i Array of , How much money can you steal at most , As long as each transition state is gradually accumulated, you can get the money that the whole array can steal .

• If the array length is 1, Only one family , It must have stolen the family , The most profitable , therefore dp[1]=nums[0]

• Every time for a family , We choose to steal him or not , If we choose to steal, then the previous one must not steal , Therefore, the maximum benefit of the accumulated superior , Similarly, if you choose not to steal him , Then we can accumulate up to one level of income . So the transfer equation is dp[i]=max(dp[i−1],nums[i−1]+dp[i−2]). there i stay dp Array length in , stay nums Middle is the subscript .

• At this time, the first house and the last house cannot get , Then we can discuss it in two situations ：

situation 1： Steal money from the first house , Don't steal the last family's money . The initial state and state transition remain unchanged , Only when traversing, the last bit of the array is not traversed .
situation 2： Steal the last one please , Don't steal money from the first house . The initial state is set dp[1]=0, Not the first one , Then, when traversing, it will also traverse to the last bit of the array .

• Finally, take the larger value of the two cases .

class Solution {
    
public:
    int rob(vector<int>& nums) {
    
        //dp[i] The length is i Array of , How much money can you steal at most 
        vector<int> dp(nums.size() + 1, 0); 
        // Choose to steal the first 
        dp[1] = nums[0]; 
        // The last one can't steal 
        for(int i = 2; i < nums.size(); i++) 
            // For each family, you can choose to steal or not 
            dp[i] = max(dp[i - 1], nums[i - 1] + dp[i - 2]); 
        int res = dp[nums.size() - 1]; 
        // eliminate dp Array , The second cycle 
        dp.clear(); 
        // Don't steal the first one 
        dp[1] = 0; 
        // You can steal the last one 
        for(int i = 2; i <= nums.size(); i++) 
            // For each family, you can choose to steal or not 
            dp[i] = max(dp[i - 1], nums[i - 1] + dp[i - 2]); 
        // Select the maximum value 
        return max(res, dp[nums.size()]); 
    }
};

Time complexity ：O(n), among n Is array length , Traverse the array twice alone
Spatial complexity ：O(n), Dynamically plan the space of auxiliary array

3、 ... and 、 The best time to buy and sell stocks ( One )

Solution 1 : Dynamic programming ( recommend )

• use dp[i][0] It means the first one i Day does not hold the maximum return until that day ,dp[i][1] It means the first one i Tian Holdings , Maximum gain to date .
• Day one does not hold shares , Then the total income is 0,dp[0][0]=0; The first day , Then the total income is the cost of buying stocks , This is a negative number ,dp[0][1]=−prices[0]
• For every day after that , If you do not hold shares on that day , It may have been sold or not bought in the past few days , So the total income so far is the same as the previous day , It may also be sold on the same day , We choose the larger state dp[i][0]=max(dp[i−1][0],dp[i−1][1]+prices[i]);
• If shares are held on the same day , It may be that I bought stocks in the previous few days , Not sold that day , So the return is the same as the day before , It is also possible to buy on the same day , At this time, the stock price with negative return , The same is to select the maximum value ：dp[i][1]=max(dp[i−1][1]−prices[i]).

class Solution {
    
public:
    int maxProfit(vector<int>& prices) {
    
        int n = prices.size();
        //dp[i][0] Indicates the maximum return of non holding shares until that day ,dp[i][1] It means holding shares one day , Maximum gain to date 
        vector<vector<int> > dp(n, vector<int>(2, 0)); 
        // Day one does not hold shares , The total revenue is 0
        dp[0][0] = 0; 
        // The first day , The total income is minus the share price of that day 
        dp[0][1] = -prices[0]; 
        // Traverse the next day , State shift 
        for(int i = 1; i < n; i++){
     
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = max(dp[i - 1][1], -prices[i]);
        }
        // Not holding shares on the last day , Maximum gain to date 
        return dp[n - 1][0]; 
    }
};

Time complexity ：O(n), among n Is array length , Traversing the array once
Spatial complexity ：O(n), Dynamically plan the space of auxiliary array

Solution 2 : greedy

If we sell shares one day , So to get the most out of it , It must be the stock it bought on the day of the lowest price in front of it . So we can use greed to solve , Subtract the daily income from the minimum price every time to maintain the maximum value .

• First, exclude the special case that the array is empty .
• Think of the first day as the lowest price , If the price is lower during subsequent traversal, the update price is the lowest .
• Each time, compare the maximum return with the price of the day minus the lowest price , Select the maximum value as the maximum benefit .

class Solution {
    
public:
    int maxProfit(vector<int>& prices) {
    
        // Maintain maximum benefits 
        int res = 0; 
        // Exclude special circumstances 
        if(prices.size() == 0) 
            return res;
        // Maintain the minimum stock price 
        int Min = prices[0]; 
        // Traverse subsequent stock prices 
        for(int i = 1; i < prices.size(); i++){
     
            // If the price of the day is lower, update the lowest price 
            Min = min(Min, prices[i]); 
            // Maintenance maximum 
            res = max(res, prices[i] - Min); 
        }
        return res;
    }
};

Time complexity ：O(n), among n Is array length , Traverse the array at once
Spatial complexity ：O(1), Constant level variable , No additional auxiliary space