力扣刷题记录（22）LeetCode：714、300、674

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

直接分析状态：

1.持有股票

• ?可以是持续上一次持有股票的状态
• 可以是买入当前股票

2.不持有股票

• 可以是持续上一次不持有股票的状态
• 可以是卖出当前股票?

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

300.?最长递增子序列?

?dp表示当前区间内最长递增子序列的长度，在满足当前nums值大于区间内某一nums值的前提下，寻找当前区间内最长递增子序列的长度。dp[i]=max(dp[i],dp[j]+1)

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

674.?最长连续递增序列

声明数组dp，表示当前区间最长连续递增序列的长度。如果当前nums值大于前一个nums值，那么当前区间?最长连续递增序列的长度就等于前一个的长度加1

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        vector<int> dp(nums.size(),1);
        int ans=1;
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i]>nums[i-1])
                dp[i]=dp[i-1]+1;
            ans=max(ans,dp[i]);
        }
        return ans;
    }
};