经典问题
简述：存在股票的价格数组，只能选择某一天买入的股票，并在未来某一个不同的日子卖出，计算最大利润。
思路
关键思路在于：”买入卖出“ >> “持有不持有”，因为dp记录状态的时候，“持有不持有”才是一种持续的状态，即额外记录状态即可
动态规划五部曲分析：
1、确定dp数组以及下标的含义
dp[i][0]表示第i天持有股票的最多现金；dp[i][1]表示第i天不持有股票的最多现金；买入时扣除花费金额
2、确定递推公式
- 第i天持有股票dp[i][0]可由以下两者状态所致
- 第i-1天就已经持有，保持现状，即dp[i-1][0]
- 第i天买入，即-price[i]（股票价格）
- 即dp[i][0] = max(dp[i-1][0], -price[0])
- 第i天不持有股票dp[i][1]可由两者状态所致
- 第i-1天就已经不持有，保持现状，即dp[i-1][1]
- 第i天卖出了股票，即dp[i-1][0] + price[i]
- 即dp[i][1] = max(dp[i-1][1], dp[i-1][0]+price[i])
3、dp数组如何初始化
基础在于dp[0][0]和dp[0][1]，即dp[0][0]=-price[0]，dp[0][1]=0
4、确定遍历顺序，即从前向后
5、举例推导dp数组
注：链接中图解更方便理解
拓展题型
股票买卖的最佳时机II
约束条件：可以多次交易，但不准同时持有多支股票
解题思路：递归公式的改变
- 即dp[i][0] = max(dp[i-1][0], dp[i-1][1]-price[i])
股票买卖的最佳时机III
约束条件：最多买入K次股票，不准同时持有多支股票
解题思路：
- K为2时的情况
- 分为5个状态，分别为没有操作、第一次买入、第一次卖出、第二次买入、第二次卖出；即dp[i][j]表示第i天，j为[0-4]五个状态
- dp[i][1] = max(dp[i-1][0] - price[i], dp[i-1][1])
- dp[i][2] = max(dp[i-1][1] + price[i], dp[i-1][2])（同理可得dp[i][3]和dp[i][4]）
- K可为任何值时的通解
- 参考上述K=2时可以得出状态数为2*K+1个，分别讨论即可
