动态规划之股票问题大总结

参考资料：代码随想录 (programmercarl.com)

一、只能买卖一次

题目链接：121. 买卖股票的最佳时机 - 力扣（LeetCode）

算法思想：

设置两种状态:0表示已持有股票，1表示未持有股票
1.dp[i][0]表示第i天已持有股票时，获得的最大利润
dp[i][1]表示第i天未持有股票时，获得的最大利润
2.递推式:
对于dp[i][0]:
若第i-1天已持有股票，则dp[i][0]=dp[i-1][0];
若第i-1天未持有股票，则dp[i][0]=0-prices[i];
综上,dp[i][0]=fmax(dp[i-1][0],-prices[i]);
对于dp[i][1]:
若第i-1天未持有股票，则dp[i][1]=dp[i-1][1];
若第i-1天已持有股票，则dp[i][1]=dp[i-1][0]+prices[i];
综上:dp[i][1]=fmax(dp[i-1][1],dp[i-1][0]+prices[i]);
3.初始化:
dp[0][0]=-prices[0];

算法实现：

int maxProfit(int *prices,int pricesSize){//设置两种状态:0表示已持有股票，1表示未持有股票//1.dp[i][0]表示第i天已持有股票时，获得的最大利润//dp[i][1]表示第i天未持有股票时，获得的最大利润//2.递推式://对于dp[i][0]://      若第i-1天已持有股票，则dp[i][0]=dp[i-1][0];//      若第i-1天未持有股票，则dp[i][0]=0-prices[i];//综上,dp[i][0]=fmax(dp[i-1][0],-prices[i]);//对于dp[i][1]://      若第i-1天未持有股票，则dp[i][1]=dp[i-1][1];//      若第i-1天已持有股票，则dp[i][1]=dp[i-1][0]+prices[i];//综上:dp[i][1]=fmax(dp[i-1][1],dp[i-1][0]+prices[i]);//3.初始化://dp[0][0]=-prices[0];int dp[pricesSize][2];memset(dp,0,sizeof(dp));dp[0][0]=-prices[0];for(int i=1;i<pricesSize;i++){dp[i][0]=fmax(dp[i-1][0],-prices[i]);dp[i][1]=fmax(dp[i-1][1],dp[i-1][0]+prices[i]);}return dp[pricesSize-1][1];
}

二、可以买卖多次

题目链接：122. 买卖股票的最佳时机 II - 力扣（LeetCode）

算法思想：

设置两种状态:0表示已持有股票，1表示未持有股票
1.dp[i][0]表示第i天已持有股票时，获得的最大利润
dp[i][1]表示第i天未持有股票时，获得的最大利润
2.递推式:
对于dp[i][0]:
若第i-1天已持有股票，则dp[i][0]=dp[i-1][0];
若第i-1天未持有股票，则dp[i][0]=dp[i-1][1]-prices[i];
综上,dp[i][0]=fmax(dp[i-1][0],dp[i-1][1]-prices[i]);
(II与I的唯一区别就在于:
只允许一次购买时,在持有股票之前，所获得利润必为0,而允许多次购买则不然)
对于dp[i][1]:
若第i-1天未持有股票，则dp[i][1]=dp[i-1][1];
若第i-1天已持有股票，则dp[i][1]=dp[i-1][0]+prices[i];
综上:dp[i][1]=fmax(dp[i-1][1],dp[i-1][0]+prices[i]);
3.初始化:
dp[0][0]=-prices[0];

算法实现：

int maxProfitII(int *prices,int pricesSize){//设置两种状态:0表示已持有股票，1表示未持有股票//1.dp[i][0]表示第i天已持有股票时，获得的最大利润//dp[i][1]表示第i天未持有股票时，获得的最大利润//2.递推式://对于dp[i][0]://      若第i-1天已持有股票，则dp[i][0]=dp[i-1][0];//      若第i-1天未持有股票，则dp[i][0]=dp[i-1][1]-prices[i];//综上,dp[i][0]=fmax(dp[i-1][0],dp[i-1][1]-prices[i]);//(II与I的唯一区别就在于://        只允许一次购买时,在持有股票之前，所获得利润必为0,而允许多次购买则不然)//对于dp[i][1]://      若第i-1天未持有股票，则dp[i][1]=dp[i-1][1];//      若第i-1天已持有股票，则dp[i][1]=dp[i-1][0]+prices[i];//综上:dp[i][1]=fmax(dp[i-1][1],dp[i-1][0]+prices[i]);//3.初始化://dp[0][0]=-prices[0];int dp[pricesSize][2];memset(dp,0,sizeof(dp));dp[0][0]=-prices[0];for(int i=1;i<pricesSize;i++){dp[i][0]=fmax(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]=fmax(dp[i-1][1],dp[i-1][0]+prices[i]);}return dp[pricesSize-1][1];
}

三、最多买卖两次

题目链接：123. 买卖股票的最佳时机 III - 力扣（LeetCode）

算法思想：

设置四种状态:
0表示第一次已持有股票
1表示第一次未持有股票
2表示第二次已持有股票
3表示第二次未持有股票
1.dp[i][0]表示第i天第一次已持有股票时，获得的最大利润
dp[i][1]表示第i天第一次未持有股票时，获得的最大利润
dp[i][2]表示第i天第二次已持有股票时，获得的最大利润
dp[i][3]表示第i天第二次未持有股票时，获得的最大利润
2.递推式:
对于dp[i][0]:
若第i-1天第一次已持有股票，则dp[i][0]=dp[i-1][0];
若第i-1天第一次未持有股票，则dp[i][0]=0-prices[i];
综上,dp[i][0]=fmax(dp[i-1][0],-prices[i]);
对于dp[i][1]:
若第i-1天第一次未持有股票，则dp[i][1]=dp[i-1][1];
若第i-1天第一次已持有股票，则dp[i][1]=dp[i-1][0]+prices[i];
综上,dp[i][1]=fmax(dp[i-1][1],dp[i-1][0]+prices[i]);
对于dp[i][2]:
若第i-1天第一次已持有股票，则dp[i][2]=dp[i-1][2];
若第i-1天第一次未持有股票，则dp[i][2]=dp[i-1][1]-prices[i];
综上,dp[i][2]=fmax(dp[i-1][2],dp[i-1][1]-prices[i]);
对于dp[i][3]:
若第i-1天第一次未持有股票，则dp[i][3]=dp[i-1][3];
若第i-1天第一次已持有股票，则dp[i][3]=dp[i-1][2]+prices[i];
综上:dp[i][3]=fmax(dp[i-1][3],dp[i-1][2]+prices[i]);
3.初始化:
dp[0][0]=dp[0][2]=-prices[0];

算法实现：

int maxProfitIII(int *prices,int pricesSize){//设置四种状态://    0表示第一次已持有股票//    1表示第一次未持有股票//    2表示第二次已持有股票//    3表示第二次未持有股票//1.dp[i][0]表示第i天第一次已持有股票时，获得的最大利润//dp[i][1]表示第i天第一次未持有股票时，获得的最大利润//dp[i][2]表示第i天第二次已持有股票时，获得的最大利润//dp[i][3]表示第i天第二次未持有股票时，获得的最大利润//2.递推式://对于dp[i][0]://      若第i-1天第一次已持有股票，则dp[i][0]=dp[i-1][0];//      若第i-1天第一次未持有股票，则dp[i][0]=0-prices[i];//综上,dp[i][0]=fmax(dp[i-1][0],-prices[i]);//对于dp[i][1]://      若第i-1天第一次未持有股票，则dp[i][1]=dp[i-1][1];//      若第i-1天第一次已持有股票，则dp[i][1]=dp[i-1][0]+prices[i];//综上,dp[i][1]=fmax(dp[i-1][1],dp[i-1][0]+prices[i]);//对于dp[i][2]://      若第i-1天第一次已持有股票，则dp[i][2]=dp[i-1][2];//      若第i-1天第一次未持有股票，则dp[i][2]=dp[i-1][1]-prices[i];//综上,dp[i][2]=fmax(dp[i-1][2],dp[i-1][1]-prices[i]);//对于dp[i][3]://      若第i-1天第一次未持有股票，则dp[i][3]=dp[i-1][3];//      若第i-1天第一次已持有股票，则dp[i][3]=dp[i-1][2]+prices[i];//综上:dp[i][3]=fmax(dp[i-1][3],dp[i-1][2]+prices[i]);//3.初始化://dp[0][0]=dp[0][2]=-prices[0];int dp[pricesSize][4];memset(dp,0,sizeof(dp));dp[0][0]=dp[0][2]=-prices[0];for(int i=1;i<pricesSize;i++){dp[i][0]=fmax(dp[i-1][0],-prices[i]);dp[i][1]=fmax(dp[i-1][1],dp[i-1][0]+prices[i]);dp[i][2]=fmax(dp[i-1][2],dp[i-1][1]-prices[i]);dp[i][3]=fmax(dp[i-1][3],dp[i-1][2]+prices[i]);}return dp[pricesSize-1][3];
}

四、最多买卖k次

题目链接：188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

算法思想：

设置2*k种状态:
for j=1 to k
2*j-1表示第j次已持有股票
2*j+1表示第j次未持有股票
1.dp[i][2*j-1]表示第i天第j次已持有股票时，获得的最大利润
dp[i][2*j]表示第i天第j次未持有股票时，获得的最大利润
2.递推式:
对于dp[i][2*j-1]:
若第i-1天第j次已持有股票，则dp[i][2*j-1]=dp[i-1][2*j-1];
若第i-1天第j次未持有股票，则dp[i][2*j-1]=dp[i-1][2*j-2]-prices[i];
综上,dp[i][2*j-1]=fmax(dp[i-1][2*j-1],dp[i-1][2*j-2]-prices[i]);
对于dp[i][2*j]:
若第i-1天第j次未持有股票，则dp[i][2*j]=dp[i-1][2*j];
若第i-1天第j次已持有股票，则dp[i][2*j]=dp[i-1][2*j-1]+prices[i];
综上,dp[i][2*j]=fmax(dp[i-1][2*j],dp[i-1][2*j-1]+prices[i]);
3.初始化:
for(int i=1;i<=2*k;i+=2) dp[0][i]=-prices[0];

算法实现：（实际上就是在三的基础上，从2次买卖延伸到了k次买卖，用for循环即可）

int maxProfitIV(int k,int *prices,int pricesSize){//设置2*k种状态://    for j=1 to k//      2*j-1表示第j次已持有股票//      2*j+1表示第j次未持有股票//1.dp[i][2*j-1]表示第i天第j次已持有股票时，获得的最大利润//dp[i][2*j]表示第i天第j次未持有股票时，获得的最大利润//2.递推式://对于dp[i][2*j-1]://      若第i-1天第j次已持有股票，则dp[i][2*j-1]=dp[i-1][2*j-1];//      若第i-1天第j次未持有股票，则dp[i][2*j-1]=dp[i-1][2*j-2]-prices[i];//综上,dp[i][2*j-1]=fmax(dp[i-1][2*j-1],dp[i-1][2*j-2]-prices[i]);//对于dp[i][2*j]://      若第i-1天第j次未持有股票，则dp[i][2*j]=dp[i-1][2*j];//      若第i-1天第j次已持有股票，则dp[i][2*j]=dp[i-1][2*j-1]+prices[i];//综上,dp[i][2*j]=fmax(dp[i-1][2*j],dp[i-1][2*j-1]+prices[i]);//3.初始化://for(int i=1;i<=2*k;i+=2) dp[0][i]=-prices[0];int dp[pricesSize][2*k+1];memset(dp,0,sizeof(dp));for(int i=1;i<=2*k;i+=2)dp[0][i]=-prices[0];for(int i=1;i<pricesSize;i++){for(int j=1;j<=k;j++){dp[i][2*j-1]=fmax(dp[i-1][2*j-1],dp[i-1][2*j-2]-prices[i]);dp[i][2*j]=fmax(dp[i-1][2*j],dp[i-1][2*j-1]+prices[i]);}}return dp[pricesSize-1][2*k];
}

五、买卖多次，卖出有一天冷冻期

题目链接：309. 最佳买卖股票时机含冷冻期 - 力扣（LeetCode）

算法思想：

设置三种状态:
0表示已持有股票
1表示未持有股票且处于非冷冻状态
2表示未持有股票且处于冷冻状态
1.dp[i][0]表示第i天已持有股票时，获得的最大利润
dp[i][1]表示第i天未持有股票且处于非冷冻状态时，获得的最大利润
dp[i][2]表示第i天未持有股票且处于冷冻状态时，获得的最大利润
2.递推式:
对于dp[i][0]:
若第i-1天已持有股票，则dp[i][0]=dp[i-1][0];
若第i-1天未持有股票，必为非冷冻状态，则dp[i][0]=dp[i-1][1]-prices[i];
综上,dp[i][0]=fmax(dp[i-1][0],dp[i-1][1]-prices[i]);
对于dp[i][1]:
第i-1天必未持有股票
若第i-1天未持有股票且处于非冷冻状态，则dp[i][1]=dp[i-1][1];
若第i-1天未持有股票且处于冷冻状态，则dp[i][1]=dp[i-1][2];
综上:dp[i][1]=fmax(dp[i-1][1],dp[i-1][2]);
对于dp[i][2]:
第i-1天必已持有股票，则dp[i][2]=dp[i-1][0]+prices[i];
3.初始化:
dp[0][0]=-prices[0];

算法实现：

int maxProfitV(int *prices,int pricesSize){//设置三种状态://      0表示已持有股票//      1表示未持有股票且处于非冷冻状态//      2表示未持有股票且处于冷冻状态//1.dp[i][0]表示第i天已持有股票时，获得的最大利润//dp[i][1]表示第i天未持有股票且处于非冷冻状态时，获得的最大利润//dp[i][2]表示第i天未持有股票且处于冷冻状态时，获得的最大利润//2.递推式://对于dp[i][0]://      若第i-1天已持有股票，则dp[i][0]=dp[i-1][0];//      若第i-1天未持有股票，必为非冷冻状态，则dp[i][0]=dp[i-1][1]-prices[i];//综上,dp[i][0]=fmax(dp[i-1][0],dp[i-1][1]-prices[i]);//对于dp[i][1]://      第i-1天必未持有股票//      若第i-1天未持有股票且处于非冷冻状态，则dp[i][1]=dp[i-1][1];//      若第i-1天未持有股票且处于冷冻状态，则dp[i][1]=dp[i-1][2];//综上:dp[i][1]=fmax(dp[i-1][1],dp[i-1][2]);//对于dp[i][2]://      第i-1天必已持有股票，则dp[i][2]=dp[i-1][0]+prices[i];//3.初始化://dp[0][0]=-prices[0];int dp[pricesSize][3];memset(dp,0,sizeof(dp));dp[0][0]=-prices[0];for(int i=1;i<pricesSize;i++){dp[i][0]=fmax(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]=fmax(dp[i-1][1],dp[i-1][2]);dp[i][2]=dp[i-1][0]+prices[i];}return fmax(dp[pricesSize-1][1],dp[pricesSize-1][2]);
}

六、买卖多次，卖出有手续费

题目链接：714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）

算法思想：（同二）

算法实现：（如果掌握了二，那么这题就不用看）

int maxProfitVI(int *prices,int pricesSize,int fee){//设置两种状态:0表示已持有股票，1表示未持有股票//1.dp[i][0]表示第i天已持有股票时，获得的最大利润//dp[i][1]表示第i天未持有股票时，获得的最大利润//2.递推式://对于dp[i][0]://      若第i-1天已持有股票，则dp[i][0]=dp[i-1][0];//      若第i-1天未持有股票，则dp[i][0]=dp[i-1][1]-prices[i];//综上,dp[i][0]=fmax(dp[i-1][0],dp[i-1][1]-prices[i]);//对于dp[i][1]://      若第i-1天未持有股票，则dp[i][1]=dp[i-1][1];//      若第i-1天已持有股票，则dp[i][1]=dp[i-1][0]+prices[i]-fee;//综上:dp[i][1]=fmax(dp[i-1][1],dp[i-1][0]+prices[i]-fee);//3.初始化://dp[0][0]=-prices[0];int dp[pricesSize][2];memset(dp,0,sizeof(dp));dp[0][0]=-prices[0];for(int i=1;i<pricesSize;i++){dp[i][0]=fmax(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]=fmax(dp[i-1][1],dp[i-1][0]+prices[i]-fee);}return dp[pricesSize-1][1];
}