总体思路
有过在 Leetcode 上练习经历的同学们对股票问题肯定不会感到陌生, 动态规划问题的核心在于寻找状态转移方程, 对于常规的动态规划问题, 如零钱问题, 背包问题, 我们可能会觉得状态转移方程找起来并不费劲, 但对于股票问题, 可能很多同学都觉得状态转移方程难找. 在我对股票问题进行了反复研究之后, 我发现其实之所以股票系列分析存在这种困难, 并不是 "转移方程难找", 而是其具有多个维度的 "状态", 其状态的复杂性导致我们在没有处理好状态的情况下便谈不上解决 "转移方程" 的问题.
状态的确定与处理?
首先我们要考虑的是状态有哪些, 具体到本题, 共有三个维度的状态:
天数
允许交易的最大次数
用户账户当前状态 (持有或者未持有股票)
其次是如何处理状态, 其实大家可以细细回想, 对于动态规划问题我们处理状态, 虽然你可能没有注意, 其实使用的是 "穷举" 思想, 比如说背包问题中的物品数量和背包容量. 至于怎么枚举, 看下面的伪代码你肯定就明白啦!
for 状态 1 in 状态 1 的所有取值:
for 状态 2 in 状态 2 的所有取值:
for ...
dp[状态 1][状态 2][...] = 择优 (选择 1, 选择 2...)
该伪代码参考自 Leetcode, 个人认为这个状态枚举思路的伪代码写的非常好, 但是作者对于股票问题状态划分有些复杂.
那具体到本题, 我们的状态框架如下
- dp[i][k][0 or 1] // 前面说了三个维度, 自然 dp 数组也是三维的
- for(int i = 0;i <n;i++)
- for(int j = 0;j < k;j++)
dp[i][j][0] 取优
dp[i][j][1] 取优 // 账户状态这个维度只有两种可能, 就直接计算就好啦.
那我们接下里将通过对股票问题的具体实例讲解的方式来介绍具体解法, 目前剩下的其实就是个状态转移方程的事情啦.
各个击破
k = 1 的情况
121. 买卖股票的最佳时机
k = 1 是思路很清晰, 其实只需要直接一趟遍历, 并且记录下当前元素之前的最小元素并利用其计算当前天卖出最大收益即可. 这个其实感觉不算典型动态规划.
- class Solution {
- public int maxProfit(int[] prices) {
- if(prices == null || prices.length == 0)
- return 0;
- int min = prices[0],max = 0;
- for(int i = 1;i < prices.length;i++){
- max = Math.max(max,prices[i] - min);
- min = Math.min(min,prices[i]);
- }
- return max;
- }
- }
k 值不受限
122. 买卖股票的最佳时机 II
枚举框架
按照我们最开始的状态枚举框架, k 不受限即从前向后遍历 (了解完全背包问题的同学肯定熟悉), 并且不设置 k 维度即可 (只有天数, 账户状态两个维度).
状态转移方程
当前天未持有, 则有两种情况:
1, 昨天就未持有, 今天也不买, 则为 dp[i - 1][0]
2, 昨天持有, 今天卖出, 则为 dp[i - 1][1] + prices[i])
综上, 二者取优
dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] + prices[i]);
同样, 当前天持有也是两种情况:
1, 昨天持有, 则为 dp[i - 1][1]
2, 昨天未持有, 今天买入 dp[i - 1][0] - prices[i]
综上, 二者取优
- dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
- class Solution {
- public int maxProfit(int[] prices) {
- int[][] dp = new int[prices.length][2];//0 为未持有, 1 为持有
- dp[0][0] = 0;
- dp[0][1] = 0 - prices[0];
- for(int i = 1;i < prices.length;i++){
- dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] + prices[i]);
- dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
- }
- return dp[prices.length - 1][0];
- }
- }
k 值不受限且包含冷冻期
309. 最佳买卖股票时机含冷冻期
枚举框架
按照我们最开始的状态枚举框架, k 不受限即从前向后遍历 (了解完全背包问题的同学肯定熟悉), 并且不设置 k 维度即可 (只有天数, 账户状态两个维度).
状态转移方程
当前天未持有, 则有两种情况:
1, 昨天就未持有, 今天也不买, 则为 dp[i - 1][0]
2, 昨天持有, 今天卖出, 则为 dp[i - 1][1] + prices[i - 1]), 注意, price 从 0 开始索引
综上, 二者取优
dp[i][0] = Math.max(dp[i - 1][1] + prices[i - 1],dp[i - 1][0]);
同样, 当前天持有也是两种情况, 但由于存在冷冻期, 买出的话需要从 i-2 转移过来:
1, 昨天持有, 则为 dp[i - 1][1]
2, 昨天未持有, 今天买入 dp[i - 2][0] - prices[i - 1]
综上, 二者取优
- dp[i][1] = Math.max(dp[i - 1][1],i - 2>= 0 ? dp[i - 2][0] - prices[i - 1]: 0 - prices[i - 1])
- class Solution {
- public int maxProfit(int[] prices) {
- int[][] dp = new int[prices.length + 1][2];
- dp[0][1] = Integer.MIN_VALUE;
- for(int i = 1;i <= prices.length;i++){
- dp[i][0] = Math.max(dp[i - 1][1] + prices[i - 1],dp[i - 1][0]);
- dp[i][1] = Math.max(dp[i - 1][1],i - 2 >= 0 ? dp[i - 2][0] - prices[i - 1]: 0 - prices[i - 1]);
- }
- return dp[prices.length][0];
- }
- }
k 值不受限且包含手续费
状态转移方程与 k 值不受限完全相同, 只是卖出时要减手续费即可
枚举框架
按照我们最开始的状态枚举框架, k 不受限即从前向后遍历 (了解完全背包问题的同学肯定熟悉), 并且不设置 k 维度即可 (只有天数, 账户状态两个维度).
状态转移方程
当前天未持有, 则有两种情况:
1, 昨天就未持有, 今天也不买, 则为 dp[i - 1][0]
2, 昨天持有, 今天卖出, 则为 dp[i - 1][1] + prices[i] - fee)
综上, 二者取优
dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] + prices[i] - fee);
同样, 当前天持有也是两种情况:
1, 昨天持有, 则为 dp[i - 1][1]
2, 昨天未持有, 今天买入 dp[i - 1][0] - prices[i]
综上, 二者取优
- dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
- class Solution {
- public int maxProfit(int[] prices, int fee) {
- int[][] dp = new int[prices.length][2];//0 为未持有, 1 为持有
- dp[0][0] = 0;
- dp[0][1] = 0 - prices[0];
- for(int i = 1;i < prices.length;i++){
- dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] + prices[i] - fee);
- dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
- }
- return dp[prices.length - 1][0];
- }
- }
k 为任意整数
188. 买卖股票的最佳时机 IV
枚举框架
枚举框架与本文最开始分析的思路完全相同, 只需要对天, 最大交易次数, 账户状态这三个维度进行枚举即可.
状态转移方程
当前天未持有, 则有两种情况:
1, 昨天就未持有, 今天也不买, 且显然这种情况不会增加交易次数, 则为 dp[i - 1][j][0]
2, 昨天持有, 今天卖出, 卖出操作并不会增加交易次数, 仍然是本交易次数维度进行转移, 为 dp[i - 1][j][1] + prices[i]
综上, 二者取优
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
同样, 当前天持有也是两种情况:
1, 昨天持有, 则为 dp[i - 1][j][1]
2, 昨天未持有, 今天买入, 注意买入会引起交易次数变化, 所以为 dp[i - 1][j - 1][0] - prices[i]
综上, 二者取优
- dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
- class Solution {
- public int maxProfit(int k, int[] prices) {
- if(prices == null || prices.length < 2)
- return 0;
- int[][][] dp = new int[prices.length][k + 1][2];//0 是未持有, 1 是持有
- for(int i = 0;i <= k;i++){// 第一天 base case
- dp[0][i][1] = 0 - prices[0];
- }
- for(int i = 1;i < prices.length;i++){
- for(int j = 1;j <= k;j++){
- dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
- dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
- }
- }
- return dp[prices.length - 1][k][0];
- }
- }
总结
看到这里, 其实我们就会明白, 动态规划其实要确定的三部分就是:
dp 语义
状态枚举框架
转移方程
确定了这三样, 一切便都迎刃而解了.
来源: https://www.cnblogs.com/wunsiang/p/12771442.html