3.6 log | 309.最佳买卖股票时机含冷冻期，714.买卖股票的最佳时机含手续费，300.最长递增子序列

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

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len=prices.size();
        vector<vector<int>> dp(len,vector<int>(4,0));
        dp[0][0]=0;
        dp[0][1]=0;
        dp[0][2]=-prices[0];
        dp[0][3]=0;
        for(int i=1;i<len;i++){
            dp[i][0]=dp[i-1][2]+prices[i];
            dp[i][1]=max(dp[i-1][3],dp[i-1][1]);
            dp[i][2]=max(dp[i-1][2],max(dp[i-1][3]-prices[i],dp[i-1][1]-prices[i]));
            dp[i][3]=dp[i-1][0];
        }
        return max(dp[len-1][0],max(dp[len-1][1],dp[len-1][3]));
    }
};

这道题添加了冷冻期，卖了的第二天不能交易，处于冷冻期，所以把一天分为四个状态，dp[i][0]表示当天卖出，dp[i][1]表示卖出天数>1,dp[i][2]表示持有状态，dp[i][3]表示当前处于冷冻期，这四种状态包括了所有可能状态

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

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int len= prices.size();
        vector<vector<int>> dp(len,vector<int>(2,0));
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        for(int i=1;i<len;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[len-1][0];
    }
};

这道题可以多次买卖，不过买卖一次要给一次的手续费，只需要在当天卖出股票状态时减去fee就能把解决

300.最长递增子序列

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len=nums.size();
        vector<int> dp(len,1);
        dp[0]=1;
        int result=0;
        for(int i=0;i<len;i++){
            for(int j=0;j<i;j++){
                if(nums[j]< nums[i]) dp[i]=max(dp[i],dp[j]+1);
            }
            result=max(result,dp[i]);
        }
        return result;
    }
};

这道题dp[i]的含义为以nums[i]结尾的最长子序列长度，dp[i][的初始化为全为1，因为子序列至少长度为1，递推公式为dp[i]=max(dp[i],dp[j]+1),i从前向后遍历，j在[0,i)的范围内遍历，每一个dp[i]都要比较，选出最大值返回