day41

买卖股票的三道题（最多交易1次，2次，不限次数）--动态规划法
最多交易1次：
//动态规划解题（其实贪心会更简单）
        //dp[i][0]:第i天持有股票的最大利润（持有不代表今天买入）
        //dp[i][1]:第i天不持有股票的最大利润
        //递推公式：
        //当天仍然持有，要么是前面买入的，要么是今天刚买入的
        //dp[i][0] = max(dp[i-1][0], -prices[i]);
        //当天不再持有，要么是前面就已经不持有（没买过或者已经卖了），要么是今天卖了
        //dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
        //初始化：dp[0][0] = -prices[0]; dp[0][1] = 0;

交易不限次数：
与交易1次唯一不同的点是
//当天仍然持有，要么是前面买入的，要么是今天刚买入的(今天可能不是第一次买了)
        //dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]);

最多交易两次：
//动态规划，最多只能买卖两次--分情况考虑
        //每天可能处在5种状态
        //dp[i][0]：没有操作（其实可以不写，后面4种情况包含了当天啥也没干的情况）
        //dp[i][1]：第一次持有股票，要么今天刚买入，要么前面已经买入，但还没卖过
        //dp[i][2]：第一次不持有，要么今天第一回卖出，要么前面已经卖了一回了，今天啥也没干
        //dp[i][3]：第二次持有，要么今天第二次买入，要么前面已经买了第二次了，到今天还没卖
        //dp[i][4]：第二次不持有，要么今天第二次卖出，要么前面已经卖第二次了，今天啥也没干
        //递推公式：
            dp[i][0] = dp[i-1][0];
            dp[i][1] = max(-prices[i], dp[i-1][1]);
            dp[i][2] = max(dp[i-1][1] + prices[i], dp[i-1][2]);
            dp[i][3] = max(dp[i-1][2] - prices[i], dp[i-1][3]);
            dp[i][4] = max(dp[i-1][3] + prices[i], dp[i-1][4]);
        //初始化：dp[0][0] = 0; dp[0][1] = -prices[0]; dp[0][2] = 0;//今天买今天卖
        //dp[0][3] = -prices[0];今天第二回买。dp[0][4] = 0;//今天第二回卖