给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例1:
输入:k = 2, prices = [2,4,1]
输出:2
解释:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得的利润 = 4-2 = 2 。
示例2:
输入:k = 2, prices = [3,2,6,5,0,3]
输出:7
解释:在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得的利润 = 6-2 = 4 。
随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3
对于这种什么时候该做什么决策可以获得最大值的问题,我们都可以用动态规划解决,首先看下我们初始状态有哪些维度
(1)当前是第几天,我们用index表示当前是交易的第几天
(2)当前是持有股票还是不持有股票,我们用status来代表持股状态,status=0代表不持有股票,status=1代表持有股票
(3)当前已经完成了几次交易,我们用count表示当前已经完成了几次交易
(4)当前的利润是多少,我们用profit表示
ok,现在有了这些状态之后是我们该如何做决策的时候了,那目前我们假设处于index天,当前持有股票的状态是status,当前已经完成了count次交易,当前的利润是profit,那么我们可以做的选择有哪些呢?
(1)如果status=0 也就是说我们不持有股票,那我们可以做的操作有两种,第一 我们可以选择买入股票,重新计算profit,profit=profit-prices[index],此时交易次数count不变,因为一次买入和一次卖出才算一次交易,status需要变成持有股票status=1,第二 我们可以选择不买也不卖,就是原地不动等待机会,那么这个时候这些状态都不会变化除了天数会+1
(2)如果status=1,也就是说我们持有股票,那么我们可以做的操作有两种,第一,我们可以选择卖出股票,此时profit=profit+prices[index],status=status-1,count=count+1;第二我们可以保持不动,除了index+1 其他的不变
好了,现在可以做的选择有上面四个情况,那么我们什么时候结束呢?
(1)count==k,代表目前已经完成了k次交易,我们需要停止
(2)index=len(prices),代表此时已经过完了最后一天
这两个结束条件之后我们可以计算当前的profit跟最大的profit对比,保存最大的profit
var maxProfitNum intfunc maxProfit(k int, prices []int) int {tmaxProfitNum = 0tDfsMaxProfit(0,0,0,k,prices,0)tturn maxProfitNum}func DfsMaxProfit(index int,status int,count int,k int,prices []int,profit int){t// 当前的状态如下t// index 当前是第几天t// status 当前状态是持有股票(可以卖出) 不持有股票(可以买入)t// count 当前已经完成了几次交易t// k 一共可以交易k次 prices 天数 profit 当前这种行为链条的利润tif count == k index == len(prices) {ttif maxProfitNum< profit {tttmaxProfitNum = profittt}ttturnt}tif status ==0 {tt// 不持有股票的时候 可以选择买入ttDfsMaxProfit(index+1,1,count,k,prices,profit-prices[index])tt// 选择不动ttDfsMaxProfit(index+1,0,count,k,prices,profit)t}else{tt// 持有股票的时候tt// 选择卖出ttDfsMaxProfit(index+1,0,count+1,k,prices,profit+prices[index])tt// 选择不动ttDfsMaxProfit(index+1,1,count,k,prices,profit)t}}