动态规划之股票交易问题_用一个数组表示股票每天的价格,数组的第i个数表示股票在第i天的价格。 如果只允许

动态规划_股票问题详解

动态规划之股票的买卖_简书

Table of Contents

Best Time to Buy and Sell Stock I

Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock IV

Best Time to Buy and Sell Stock V

Best Time to Buy and Sell Stock VI

---

Best Time to Buy and Sell Stock I

用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。 如果只允许进行一次交易，也就是说只允许买一支股票并卖掉，求最大的收益。

解题思路：从前向后遍历数组，分别记录最大值和最小值，需要注意的是最大值要位于最小值后面

def stock1(prices):
    min_p, max_p = 99999999, 0
    for i in range(len(prices)):
        min_p = min(min_p, prices[i])
        max_p = max(max_p, prices[i] - min_p)
    return max_p
 
if __name__ == '__main__':
    prices=[3,5,4,9,10,2]
    d = stock1(prices)
    print d

 

Best Time to Buy and Sell Stock II

用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。交易次数不限，但一次只能交易一支股票，在买入之前手上的股票必须跑出，也就是说手上最多只能持有一支股票，求最大收益

解题思路：令dp1[i]表示第i天交易之后手头有股票的最大收益，dp2[i]表示第i天交易之后手头没有股票的最大收益，那么第i天交易之后有两种状态：有股票dp1[i], 没有股票dp2[i]

在当天交易之后手上仍持有股票的前提下，当天的交易情况有两种：

1. 手头原本没有股票，当天买入：$dp1[i]=dp2[i-1]-prices[i]$

2. 手头原本有股票，是前一次交易买入，当天没有交易操作：$dp1[i]=dp1[i-1]$

因此，$dp1[i]=max\left ( dp2[i-1]-prices[i], dp1[i-1]\right )$

同理，在当天交易之后手头没有股票，当天交易情况有两种：

1. 手头原本就没有股票，当天无交易，此时有：$dp2[i]=dp2[i-1]$

2. 手头原本有股票，当天卖出，此时有：$dp2[i]=dp1[i-1]+prices[i]$

因此，$dp2[i]=max(dp2[i-1], dp1[i-1]+prices[i])$

def stock2(prices):
    dp1 = [0] * len(prices)
    dp2 = [0] * len(prices)
    dp1[0] = -prices[0]
    for i in range(1, len(prices)):
        dp1[i] = max(dp1[i-1], dp2[i-1]-prices[i])
        dp2[i] = max(dp2[i-1], dp1[i-1]+prices[i])
    return max(dp2)
 
if __name__ == '__main__':
    prices=[3,5,4,9,2,10,2]
    d = stock2(prices)
    print d

Best Time to Buy and Sell Stock III

用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。最多交易两次，手上最多只能持有一支股票，求最大收益。

解题思路：用dp[k][i]表示第i天是第k次交易的最大收益, dp1表示交易后手头有股票，dp2表示交易后手头没有股票

状态转移方程为：

dp1[k][i]=max(dp1[k][i-1], dp2[k-1][i-1]-prices[i])

dp2[k][i]=max(dp2[k][i-1], dp1[k][i-1]+prices[i])

def stock3(prices):
    dp1 = [[0]*len(prices) for i in range(3)]
    dp2 = [[0]*len(prices) for i in range(3)]
 
    l = len(prices)
    if l < 2:
        return 0
 
    dp1[1][0] = dp1[2][0] = -prices[0]
 
    for k in range(1,3):
        for i in range(1,l):
            dp1[k][i]=max(dp1[k][i-1], dp2[k-1][i-1]-prices[i])
            dp2[k][i]=max(dp2[k][i-1], dp1[k][i-1]+prices[i])
    return dp2[-1][-1]
 
if __name__ == '__main__':
    prices=[3,5,4,9,2,10,2]
    d = stock3(prices)
    print d

/*
* params: 
* hold1: 当天是第一次交易，交易之后手头有股票
* hold2: 当天是第二次交易，交易之后手头有股票
* release1: 当天是第一次交易，交易之后手头没有股票
* release2: 当天是第二次交易，交易之后手头没有股票
* */
public static int maxProfit_3(int[] prices) {
    int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE;
    int release1 = 0, release2 = 0;
 
    for(int i = 0; i < prices.length; i++) {
        release2 = Math.max(release2, hold2 + prices[i]);
        hold2 = Math.max(hold2, release1 - prices[i]);
        release1 = Math.max(release1, hold1 + prices[i]);
        hold1 = Math.max(hold1, -prices[i]);
    }
 
    return release2;
}
 
public static int maxProfit_3_1(int[] prices) {
    if (prices == null || prices.length < 2) {
        return 0;
    }
 
    int hold1 = -prices[0], hold2 = -prices[0];
    int release1 = 0, release2 = 0;
 
    for(int i = 1; i < prices.length; i++) {
        // 顺序不会影响结果
        hold1 = Math.max(hold1, -prices[i]);
        hold2 = Math.max(hold2, release1 - prices[i]);
        release2 = Math.max(release2, hold2 + prices[i]);
        release1 = Math.max(release1, hold1 + prices[i]);
    }
 
    return release2;
}

Best Time to Buy and Sell Stock IV

用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。最多交易k次，手上最多只能持有一支股票，求最大收益。

解题思路：与交易2次的情况类似，把stockIII中的2换成k就可以了，但是k非常大的时候复杂度会不理想；为了节省空间，每次令k%=2(???)；当k>=len(prices)/2，问题转化为stock2

Best Time to Buy and Sell Stock V

用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。可多次交易，但股票卖出后需冷冻一天，也就是说，卖出股票的第二天不允许交易，同时手上最多只能持有一支股票，求最大收益。

解题思路：用dp1[i]和dp2[i]分别表示当天交易后手头有股票和没有股票的最大收益

dp1[i]=max(dp1[i-1], dp2[i-2]-prices[i])

dp2[i]=max(dp2[i-1], dp1[i-1]+prices[i])

public static int maxProfit_5_Cooldown(int[] prices) {
    if (prices == null || prices.length < 2) {
        return 0;
    }
    else if (prices.length == 2) {
        int dif = prices[1] - prices[0];
        return ( dif> 0) ? dif : 0;
    }
 
    int res = 0;
 
    int n = prices.length;
    int[] buy = new int[n];
    int[] sell = new int[n];
 
    buy[0] = -prices[0];
    buy[1] = Math.max(buy[0], -prices[1]);
    sell[1] = Math.max(sell[0], buy[0] + prices[1]);
 
    // 卖掉之后要冷冻一天才能再次买入
    // 循环从 2 开始遍历
 
    for(int i = 2; i < n; i++) {
        buy[i] = Math.max(buy[i-1], sell[i-2] - prices[i]);
        sell[i] = Math.max(sell[i-1], buy[i-1] + prices[i]);
 
        res = Math.max(sell[i], res);
    }
 
    return res;
}

Best Time to Buy and Sell Stock VI

用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。可多次交易，但每次交易需要缴纳手续费fee, 同时手上最多只能持有一支股票，求最大收益。

状态转移方程：

dp1[i]=max(dp1[i-1], dp2[i-1]-prices[i])

dp2[i]=max(dp2[i-1], dp1[i-1]+prices[i]-fee)

class Solution {
    public int maxProfit(int[] prices, int fee) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
 
        int res = 0;
        
        int n = prices.length;
        int[] buy = new int[n];
        int[] sell = new int[n];
 
        buy[0] = -prices[0];
        
        for(int i = 1; i < n; i++) {
            buy[i] = Math.max(buy[i-1], sell[i-1] -prices[i]);
            sell[i] = Math.max(sell[i-1], buy[i-1] + prices[i] - fee);
            
            res = Math.max(res, sell[i]);
        }
 
        return res;
    }
}