LeetCode 714. Best Time to Buy a
2018-09-18 本文已影响53人
烛火的咆哮
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每次交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
示例 :
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
注意:
- 0 < prices.length <= 50000.
- 0 < prices[i] < 50000.
- 0 <= fee < 50000.
思路:
- 动态规划求解效率最高
- 需要多个状态转移方程
- 主要学习大神代码,传送门
代码:
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
if (n < 2) {
return 0;
}
int[] hold = new int[n];
int[] notHold = new int[n];
hold[0] = -prices[0];
for (int i = 1; i < n; ++i) {
hold[i] = Math.max(hold[i - 1], notHold[i - 1] - prices[i]);
notHold[i] = Math.max(notHold[i - 1], hold[i - 1] + prices[i] - fee);
}
return notHold[n - 1];
}
详解:
- 由于大神只贴了代码,需要自己去学习理解,这里贴出自己的看法.
- 本题是买卖股票问题的扩展版,可以多次进行交易,但是每次完整的交易(买入+卖出)都需要支付手续费,且同一时间只能买一只股票,由此得到结论:
a. 卖出-买入>fee才有利润
b. 尽量减少买卖次数 - 求得动态转移方程,此处使用双方程的方式进行求解,其中
hold[]存储当前节点本金,即手里有多少钱,初始化值为-prices[0],默认设置买下第一只股票,此时手里欠款-prices[0].
notHold[]存储当前节点所获得的最大利润,即本题的返回值 - 状态转移方程实现:
hold[i] = Math.max(hold[i - 1], notHold[i - 1] - prices[i]);设置本金为前一节点的本金与前节点最大利润减去当前股票值的最大值,即将该节点设置为新的股票购入节点,或者忽略该节点.本金数组主要解决股票购入时机的问题. - 状态转移方程实现:
notHold[i] = Math.max(notHold[i - 1], hold[i - 1] + prices[i] - fee);设置最大利润为前一节点最大利润与本金+当前节点卖出价值-fee的最大值,即在当前节点进行股票变现,或者忽略该节点,最大利润数组主要解决股票卖出时机问题. - 变化表格:
| 股票价格 | 本金(hold) | 最大利润(notHold) |
|---|---|---|
| 1 | -1 | 0 |
| 3 | -1 | 0 |
| 2 | -1 | 0 |
| 8 | -1 | 5 |
| 4 | 1 | 5 |
| 9 | 1 | 8 |
在第一只股票时买入,在第四只股票是卖出,获利5.
在第5只股票时买入,此时本金为5-4=1 > -1,赋值为1,在第六只股票时卖出,得到最大利润值为8
分析:
- 设置本金状态转移方程为
E(n) = max(E(n-1),F(n-1)-prices[n]),只有当该节点之前的节点进行过股票出售,F(n-1)-prices[n]才会大于E(n-1)
设置最大利润状态转移方程为
F(n) = max (F(n-1), E(n-1)+prices[n]-fee),使用本金+当前节点出售股票获利进行比较,比前节点更多获利才会进行结算 - 本金边界为 E(0),此时F(n-1)不存在,所以直接赋值-prices[0] . 总利润边界为F(1) ,只有买入股票后才能出售,当在此节点出售时,使用 prices[1]-prices[0]-fee.
总结:
- 瞎码字,以后再补充吧
- 动态规划问题需要很好的读题+总结归纳能力.
- 该问题中,核心方程为总利润的状态转移方程,若能求出该方程,即可推导出本金是一个变化的过程,需要另写数组存储 -> 得到第二个状态转移方程
- 再见到类似题可能还是做不出来,哎好气
