【动态规划】买卖股票相关问题

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

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

题目描述：

题目分析：

1、状态分析

其实一共就只有两种状态，不是处于 持有 状态，就是处于 未持有 状态。

• f[i]表示第i天结束后，处于 持有 状态时，最大的利润
• g[i]表示第i天结束后，处于 未持有 状态时，最大的利润

2、状态转移方程

对于f[i]，有两种情况可以到达这种状态:

• 在第 i-1 天时就已处于 持有 状态，然后第 i 天啥也不干，仍然保持 持有 状态。此时的最大利润就为 f[i - 1] 
• 在 i - 1 天的时候「未持有」股票，在第 i 天买⼊股票。此时最⼤收益为 g[i - 1] - prices[i]) 

对于g[i]，也有两种情况能够到达这种状态：

• 在 i - 1 天「持有」股票，但是在第 i 天将股票卖出。此时最⼤收益为： f[i - 1]
  + prices[i] - fee) ，记得⼿续费
• 在 i - 1 天「未持有」股票，然后第 i 天啥也不⼲。此时最⼤收益为： g[i - 1] ；

可知 g[i] 就为以上两种情况下的最大值，即