【动态规划】买卖股票相关问题
一、买卖股票的最佳时机含手续费
题目描述：
题目分析：
1、状态分析
其实一共就只有两种状态，不是处于 持有 状态，就是处于 未持有 状态。
- f[i]表示第i天结束后，处于 持有 状态时，最大的利润
- g[i]表示第i天结束后，处于 未持有 状态时，最大的利润
2、状态转移方程
对于f[i]，有两种情况可以到达这种状态:
- 在第 i-1 天时就已处于 持有 状态，然后第 i 天啥也不干，仍然保持 持有 状态。此时的最大利润就为 f[i - 1]
- 在 i - 1 天的时候「未持有」股票，在第 i 天买⼊股票。此时最⼤收益为 g[i - 1] - prices[i])
可知 f[i] 就为以上两种情况下的最大值，即
f[i] = max(f[i - 1], g[i - 1] - prices[i])
对于g[i]，也有两种情况能够到达这种状态：
- 在 i - 1 天「持有」股票，但是在第 i 天将股票卖出。此时最⼤收益为： f[i - 1]+ prices[i] - fee) ，记得⼿续费
- 在 i - 1 天「未持有」股票，然后第 i 天啥也不⼲。此时最⼤收益为： g[i - 1] ；
可知 g[i] 就为以上两种情况下的最大值，即
