(51/60)买卖股票的最佳时机含冷冻期、买卖股票的最佳时机含手续费

day51

买卖股票的最佳时期含冷冻期

leetcode：309. 买卖股票的最佳时机含冷冻期

动态规划

代码实现

/*
意义：下标为i时各种情况的收益
dp[i][0] 持有
dp[i][1] 当天卖出
dp[i][2] 之前不持有
递推：
dp[i][0] = max(dp[i-1][0],dp[i-1][2] - prices[i]); // 之前持有、之前不持有且当天持有
dp[i][1] = dp[i-1][0] + prices[i]; // 当天卖出（持有->当天卖出）
dp[i][2] = max(dp[i-1][2],dp[i-1][1]); // 之前不持有、前一天当天卖出
初始化：
dp[0][0] = -prices[0];
dp[0][1] = 0; // 没意义占位
dp[0][2] = 0; 
*/

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(),vector<int>(3,0));
        dp[0][0] = -prices[0];
        for(int i = 1;i < prices.size();i++){
            dp[i][0] = max(dp[i-1][0],dp[i-1][2] - prices[i]); // 之前持有、之前不持有且当天持有
            dp[i][1] = dp[i-1][0] + prices[i]; // 当天卖出
            dp[i][2] = max(dp[i-1][2],dp[i-1][1]); // 之前不持有、前一天当天卖出
        }

        return max(dp[prices.size()-1][1],dp[prices.size()-1][2]);
    }
};

买卖股票的最佳时机含手续费

leetcode：714. 买卖股票的最佳时机含手续费

动态规划

代码实现

/*
意义：下标为i的各类型最大收益为
dp[i][0]不持有
dp[i][1]持有
递推：
dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i] - fee); // 前一天不持有、前一天持有当天卖出
dp[i][1] = max(dp[i-1][1],dp[i-1][0] - prices[i]); // 前一天持有、前一天不持有当天持有
初始化:
dp[0][0] = 0;
dp[0][1] = -prices[0];
*/

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        vector<vector<int>> dp(prices.size(),vector<int>(2,0));
        int count = 0;
        dp[0][1] = -prices[0];
        for(int i = 1;i < prices.size();i++){
            dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i] - fee);
            dp[i][1] = max(dp[i-1][1],dp[i-1][0] - prices[i]); // 前一天持有、前一天不持有当天持有
        }

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