股票买卖问题总结

问题的描述都为：给定一支股票的价格变动数组，根据相应的价格变动数组买卖股票，要求能够获得最大的利润。

条件上的改变：股票只能交易一次，股票可以交易任意次，股票可以交易常数次，股票可以交易k次，股票在卖出后的一天冷冻期不能交易，股票交易需要收取手续费。

基本的求解方式为：动态规划和贪心

LeetCode 121 买卖股票的最佳时机

121.买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

本题中智能对股票进行一次买卖，要求解最大的利润，存在两种方法。

基于动态规划实现：重点依旧是动态规划数组的定义，依旧是定义为二维的动态规划数组 dp[i][0] 表示持有股票的最大现金数， dp[i][1] 表示不持有股票的最大现金数，但是限制了交易次数为1次。相较于不限次数的交易方式区别在于动态规划数组的推导。推导过程为： dp[i][0]=max(dp[i-1][0],-prices[i]) 由于只能买入一次，在 i 天想要持有股票只能在前面买了，或者前面没买在 prices[i] 时买入。 dp[i][1]=max(dp[i-1][0]+prices[i],dp[i-1][1])
贪心实现：从前向后遍历，不断寻找相应的最小值，最小值就是买入那天的价格，在最小值后面能够使得利润最大的值就是卖出那天的价格。

int buy=prices[0],result=0;
for(int i=1;i<n;i++){
    buy=min(buy,prices[i]);
    result=max(result,prices[i]-buy);
}

或者另外一种动态规划数组的定义： dp[i] 表示在第 i 天买入能够获得最大利润，也就是考虑到卖出的那一天一定是买入股票价格后最贵的一天。

LeetCode 122 买卖股票的最佳时机II

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

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。

返回你能获得的最大利润。

在本体中对买卖的次数不做限制，依旧是动态规划和贪心两种实现方式。

基于动态规划实现：重点依旧是动态规划数组的定义，依旧是定义为二维的动态规划数组 dp[i][0] 表示持有股票的最大现金数， dp[i][1] 表示不持有股票的最大现金数，不限制交易次数。推导过程为： dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]) 在 i 天想要持有股票可以前一天就持有，也可以前一天不持有，在 prices[i] 时买入。 dp[i][1]=max(dp[i-1][0]+prices[i],dp[i-1][1])
贪心实现：要基于贪心实现就简单很多。价格数组就是一个折线图，只需要在折线图中找到全面的增区间，将这些增区间全部相加即可。 res+=max(0,prices[i]-prices[i-1]);

LeetCode 123 买卖股票的最佳时机III

123.买卖股票的最佳时机III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

此处是交易次数为常数次的情形，并且需要理解的是，此处是最多交易两笔。本题只能使用动态规划进行求解，动态规划求解的重点依旧是动态规划数组的定义。

数组定义： dp[i][5]

dp[i][0] 表示不对股票进行任何操作所持有的最大现金数，一定是为0的
dp[i][1] 表示第一次持有股票，所拥有的最大现金数（也就是当前是持有股票的，并且是在第一次买入后没有卖出的状态）
dp[i][2] 表示第一次不持有股票，所拥有的最大现金数（也就是当前是不持有股票的，也就是是在第一次买入后再卖出后的状态）
dp[i][3] 表示第二次持有股票，所拥有的最大现金数（也就是当前是持有股票的，也就是在第二次买入后没有卖出的状态）
dp[i][4] 表示第二次不持有股票，所拥有的最大现金数（也就是当前是不持有股票的，也就是是在第二次买入后再卖出后的状态）

在此基础上既可以实现动态规划数组的推导从而求解。

LeetCode 188 买卖股票的最佳时机IV

188.买卖股票的最佳时机IV

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格，和一个整型 k 。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

本题中的交易此处不再是一个常数，而是一个变量，那么也就是在上一题基础上进行了变更，只需要将动态规划数组的定义从 dp[i][5] 拓展到 dp[i][2k+1] 即可。递推公式也是相同，只需要基于循环实现即可。

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

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

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

相较于前述题目，本题的变动是最大的，在加入了冷冻期的限制后，动态规划数组的定义需要改变，同时推导方式也需要改变。

动态规划数组的定义，此处每一天存在四种状态：持有股票、不持有股票并且不是冷冻期、当天卖出股票、冷冻期

在此基础上去推导：

dp[i][0] ：可能前一天持有，也可能当天买入（前一天可能是冷冻期也可能不是） dp[i][0]=max(max(dp[i-1][0],dp[i-1][1]-peices[i]),dp[i-1][3]-prices[i])
dp[i][1] ：前一天可能是冷冻期或者不是 dp[i][1]=max(dp[i-1][1],dp[i-1][3])
dp[i][2] ：前一天必然持有股票 dp[i][1]=dp[i-1][0]+prices[i]
dp[i][3] ：前一天必然卖出股票 dp[i][3]=dp[i-1][2]

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

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

给定一个整数数组 prices ，其中 prices[i] 表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续

此处可以使用动态规划和贪心两种算法进行求解

动态规划求解：

此处使用动态规划求解，求解的方式和122.买卖股票的最佳时机II基本相同，只需要在推导过程中，若是某天卖出在计算利润时减去手续费 fee 即可。

使用贪心求解：

此处使用贪心求解较为巧妙，将手续的收取归入股票买入阶段，假设在第一天买入股票，那么 buy=prices[0]+fee 就是股票买入的花费，对数组进行遍历，

若是出现 prices[i]+fee<buy 那么说明在，在这一天买入股票成本更低，更新 buy
若是出现 prices[i]>buy 说明此时股票的价格卖出后是可以赚钱的，并且是不限制交易次数的，那么在全局最优的情况下，这部分利润一定是能够得到的，先 res+=peices[i]-buy 并且 buy=peices[i] ，不收取手续费的原因在于，并不是真的卖出后买入，在后面若是 prices[i+1]>buy 也就是在后一天卖出可以赚更多（相同处理），若是 prices[i+1]+fee<buy 说明在后一天买入成本更低，那么更新 buy

for(int i=1;i<n;i++){
    if(buy>prices[i]+fee){
        buy=prices[i]+fee;
    }else if(buy<prices[i]){
        res+=peices[i]-buy;
        buy=prices[i];
    }
}