2019-03-21 吴亲库里 库里的深夜食堂
给这是一道买卖彩票的扩展题，之前两个版本再前面的文章，这道题指定我们可以 买卖两次，但是我在购买前首先得保证我手上没有股票。求最大的利润
这道题又比之前的题目难，不过分析还是一样的，我们还是先来进行定义状态和递推的操作。
DP[i]=第i天最大收益
DP[i]=DP[i-1]+???我们根本就不知道前面的状态，是持有股票还是已经卖了，我们也不知道当前交易的次数是否达到了两次，所以这里单单定义一个一维数组是不够的。
DP[i][k][j]
//定义了一个三维数组，i表示第几天 k表示第几次交易 j表示是否持有股票然后分情况，第i天第k次都用两种情况持有股票和没有。最后再把思路转换成实现代码。
比如这里j使用0代表没有1代表持有股票，
得出第i天第k次没有股票和第i天第k次持有股票的情况
DP[i-1][k][0]
保持前一天没有股票状态不动
DP[i][k][0]=Max{
DP[i-1][k-1][1]+第i天股票价格
表示我前一天已经拥有股票了，现在把它卖掉
DP[i-1][k][1]
前一天有股票保持不动
DP[i][k][1]=Max{
DP[i-1][k-1][0]-第i天股票价格
前一天没有股票现在买了 /**
* @param Integer[] $prices
* @return Integer
*/
function maxProfit($prices) {
$res=0;
$dp[0][0][0]=0;
$dp[0][0][1]= -$prices[0];
$dp[0][1][0]= -$prices[0];
$dp[0][1][1]= -$prices[0];
$dp[0][2][0]=0;
for($i=1;$i<count($prices);$i++){
$dp[$i][0][0]=$dp[$i-1][0][0];
$dp[$i][0][1]=max($dp[$i-1][0][1],$dp[$i-1][0][0]-$prices[$i]);
$dp[$i][1][0]=max($dp[$i-1][1][0],$dp[$i-1][0][1]+$prices[$i]);
$dp[$i][1][1]=max($dp[$i-1][1][0]-$prices[$i],$dp[$i-1][1][1]);
$dp[$i][2][0]=max($dp[$i-1][2][0],$dp[$i-1][1][1]+$prices[$i]);
}
$length=count($prices)-1;
return max($res,$dp[$length][0][0],$dp[$length][1][0],$dp[$length][2][0]);
}
