动态规划 —— dp 问题-买卖股票的最佳时机含手续费_投资dp算法
江河入海，知识涌动，这是我参与江海计划的第10篇。
1. 买卖股票的最佳时机含手续费
题目链接：
714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/
2. 算法原理
状态表示：以某一个位置为结尾或者以某一个位置为起点
dp[i]表示：第i天结束之后，此时的最大利润 ：两种情况：
1. f[i]表示：第i天结束之后，处于买入状态，此时的最大利润
2. g[i]表示：第i天结束之后，处于卖出状态，此时的最大利润
2. 状态转移方程
在第i-1天处于买入状态，看买入状态能不能到自己，看卖出状态能不能到买入状态，另一个状态也是如此，一共4种状态
买入状态到 卖出状态到 买入状态 什么都不干 -prices[i](买股票) 卖出状态 +prices[i](卖股票)-fee(手续费) 什么都不干 1. f[i] = max(f[i-1],g[i-1]--prices[i])
2. g[i] = max(g[i-1],f[i-1]+prices[i]-fee)
3. 初始化 ：把dp表填满不越界，让后面的填表可以顺利进行
f[0] = --prices[0] g[0] = 0
4. 填表顺序
本题的填表顺序是：从左往右，两个表同时填
5. 返回值 ：题目要求 + 状态表示
因为是要最大利润，所以买入状态不用考虑
本题的返回值是：g[n-1]
3. 代码
动态规划的固定四步骤：1. 创建一个dp表
2. 在填表之前初始化
3. 填表（填表方法：状态转移方程）
4. 确定返回值
class Solution {public: int maxProfit(vector& prices, int fee) { int n = prices.size(); //1. 创建dp表 vectorf(n); auto g=f; //2. 在填表之前初始化 f[0]=-prices[0]; //3. 填表（填表方法：状态转移方程） for(int i=1;i<n;i++) { f[i]=max(f[i-1],g[i-1]-prices[i]); g[i]=max(g[i-1],f[i-1]+prices[i]-fee); } //4. 确定返回值 return g[n-1]; }};未完待续~
