时间序列模型

1. 本题选择在卖出股票时支付手续费

dp 五步曲：

1. 确定 dp 及其含义
2. 每天只有 2 个状态
3. dp[i]: 第 i 天持有股票获得的最大现金
4. dp[i]: 第 i 天卖出股票获得的最大现金
5. int[] dp = new int[n];
6. 递推公式
7. dpi = Math.max(dpi - 1, dpi - 1 - prices[i]);
8. 今天不买入，则保持前一天买入状态，为 dp[i] - 1
9. 今天买入，则需要在前一天卖出的基础上减去今天的股票价格，为 dp[i] - 1 - prices[i]
10. 二者，取 max
11. dp[i] = Math.max(dp[i] - 1, dp[i] - 1 + prices[i] - fee);
12. 这里要多剪去一个手续费
13. 今天不卖出，则保持前一天卖出状态，为 dp[i] - 1
14. 今天卖出，则需要在前一天买入的基础上加上今天的股票价格，再减去手续费
15. 取 max
16. 初始化
17. dp[0] = -prices[0];
18. 其他为 0
19. 顺序：从前到后
20. 打印 dp

时间序列模型

时间序列模型(给出一个序列(数组/字符串)，其中每一个元素可以认为“一天”，并且“今天”的状态只取决于“昨天”的状态（无后效性？）)

后无效性：

思路：

1. 确定dp数组dp[i][j]（第ith轮的第j种状态）;
2. 画图，千方百计的将dp[i][j]和前一轮的状态dp[i-1][j]产生关系（确定状态转移方程）;
3. 确定基础值，最后开始硬编（感觉这种模型的dp真套路，不过有时候无法通过题目定位出是这种类型的题

目）

举例说明：LC_487. 最大连续1的个数 II

代表性的题目：打家劫舍系列、股票系列，打家劫舍III运用了树形DP。

时间序列模型（状态机模型），这种类型的题目，在确定dp的数组和下标的含义之后，状态的转换可以通过话状态图得到

之后的初始化等操作也就自然就出来了。

或者说是后序遍历的深入理解吧，需要明确当前层构成的结果如何计算，以及需要向上传递什么结果。可以先从二叉树的路径问题入手理解。

原图链接：「代码随想录」知识星球