123.买卖股票的最佳时机III

文章：35. 买卖股票的最佳时机III

题目：123. 买卖股票的最佳时机 III

【思路】

本题关键在于：至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖

1.确定数组及其下标含义

0：没有操作

1：第一次持有股票

2：第一次不持有股票

3：第二次持有股票

4：第二次不持有股票

dp[i] [j]：i表示第 i 天，j为[0-4]五个状态，dp[i] [j] 表示第i天状态 j 所剩最大现金。

需要注意：dp[i] [1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区。

例如 dp[i] [1] ，并不是说 第i天一定买入股票，有可能 第 i-1天 就买入了，那么 dp[i] [1] 延续买入股票的这个状态。

2.确定递推公式

达到dp[i] [1]的两种情况：

  • 第i天买入股票，那么dp[i] [1] = dp[i-1] [0] - prices[i]
  • 第i天没有操作，而是沿用前一天买入的状态，即：dp[i] [1] = dp[i-1] [1]

因此我们可以选取这两个前置条件的最大值得到dp[i] [1]

达到dp[i] [2]的两种情况：

  • 第i天卖出股票了，那么dp[i] [2] = dp[i-1] [1] + prices[i]
  • 第i天没有操作，沿用前一天卖出股票的状态，即：dp[i] [2] = dp[i-1] [2]

因此我们可以选取这两个前置条件的最大值得到dp[i] [2]

同理可以推出剩下状态部分：

dp[i] [3] = max(dp[i-1] [3] , dp[i-1] [2]-prices[i] ) （没有操作，在不持有股票的条件下买入第二次股票）

dp[i] [4] = max(dp[i-1] [4] , dp[i-1] [3] + prices[i] ) （没有操作，在持有第二次股票的情况下卖出）

3.数组如何初始化

dp[0] [0] = 0

dp[0] [1] = -prices[0] //第一次买入

dp[0] [2] = 0 //第一次卖出，当天买当天卖

dp[0] [3] = -prices[0] //第二次买入

dp[0] [4] = 0 //第二次卖出

4.确定遍历顺序

从前往后遍历，因为dp[i],依靠dp[i-1]的数值

5.举例推导。。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxProfit(int[] prices) {
        int[][]dp =new int[prices.length][5];
        for(int i = 1 ;i<5;i+=2){
            dp[0][i] = -prices[0];
        }
        for(int i = 1;i<prices.length;i++){
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);
            dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);
            dp[i][4] = Math.max(dp[i-1][4],dp[i-1][3]+prices[i]);
        }
        return dp[prices.length-1][4];
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func maxProfit(prices []int) int {
    dp := make([][]int,len(prices))
    for i:=0 ; i < len(dp);i++{
        dp[i] = make([]int,5)
    }
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    dp[0][2] = 0
    dp[0][3] = -prices[0]
    dp[0][4] = 0
    for i:=1;i<len(prices);i++{
        dp[i][1] = max(dp[i-1][1] , dp[i-1][0] - prices[i])
        dp[i][2] = max(dp[i-1][2] , dp[i-1][1] + prices[i])
        dp[i][3] = max(dp[i-1][3] , dp[i-1][2] - prices[i])
        dp[i][4] = max(dp[i-1][4] , dp[i-1][3] + prices[i])
        
    }
    return max(dp[len(dp)-1][2],dp[len(dp)-1][4]) //这里其实直接dp[len(dp)-1][4]就可以了，4包括了2的情况
}

188.买卖股票的最佳时机IV

文章：36. 买卖股票的最佳时机IV

题目：188. 买卖股票的最佳时机 IV

【思路】

本题和上题的区别：这里要求至多有k次交易

1.确定数组及其下标的含义

dp[i] [j]：第i天的状态为j，所剩下的最大现金是dp[i] [j]

j的状态：

  • 0表示不操作
  • 1表示第一次买入
  • 2表示第一次卖出
  • 3表示第二次买入
  • 4表示第二次卖出
  • …

因此我们可以发现：除了0以外，偶数就是卖出，奇数就是买入。

题目要求至多有k笔交易，那么j 的范围就定义为2 * k + 1就可以了

2.确定递推公式

达到dp[i][1]状态，有两个具体操作：

  • 操作一：第i天买入股票了，那么dp[i] [1] = dp[i - 1] [0] - prices[i]
  • 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i] [1] = dp[i - 1] [1]

选最大的，所以 dp[i] [1] = max(dp[i - 1] [0] - prices[i], dp[i - 1] [1]);

同理dp[i][2]也有两个操作：

  • 操作一：第i天卖出股票了，那么dp[i] [2] = dp[i - 1] [1] + prices[i]
  • 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i] [2] = dp[i - 1] [2]

所以dp[i] [2] = max(dp[i - 1] [1] + prices[i], dp[i - 1] [2])

同理可以类比剩下的状态，代码如下：

1
2
3
4
for (int j = 0; j < 2 * k - 1; j += 2) {
    dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
    dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}

3.数组初始化

dp[0] [0] = 0

dp[0] [1] = -prices[0] //第一次买入

dp[0] [2] = 0 //第一次卖出，当天买当天卖

dp[0] [3] = -prices[0] //第二次买入

dp[0] [4] = 0 //第二次卖出

同理可以推出dp[0] [j]当j为奇数的时候都初始化为-prices[0]

1
2
3
for (int j = 1; j < 2 * k; j += 2) {
    dp[0][j] = -prices[0];
}

在初始化的地方同样要类比j为偶数是卖、奇数是买的状态

4.确定遍历顺序

从前往后遍历

5.举例推导。。。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxProfit(int k, int[] prices) {
        int[][] dp = new int[prices.length][2*k+1];
        for(int i =1;i<2*k;i+=2){
            dp[0][i]= -prices[0];
        }
        for(int i = 1; i < prices.length;i++){
            for(int j = 0; j < 2*k ; j+=2){
                dp[i][j+1] = Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i]);
                dp[i][j+2] = Math.max(dp[i-1][j+2],dp[i-1][j+1] + prices[i]);
            }
        }
        return dp[dp.length-1][2*k];
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func maxProfit(k int, prices []int) int {
    dp := make([][]int,len(prices))
    status := make([]int,(2*k+1)*len(prices))
    //数组初始化这一部分不是很懂
    for i := range dp{
        dp[i] = status[:2*k+1]
        status = status[2*k+1:]
    }
    for j :=1 ; j <2 *k;j+=2{
        dp[0][j] = -prices[0]
    }
    for i :=1;i<len(prices);i++{
        for j :=0;j<2*k;j+=2{
            dp[i][j+1] = max(dp[i-1][j+1],dp[i-1][j] - prices[i])
            dp[i][j+2] = max(dp[i-1][j+2],dp[i-1][j+1] + prices[i])
        }
    }
    return dp[len(prices)-1][2*k]
}

【算法总结】

  • 股票问题：类比j为偶数是卖、奇数是买的状态

  • 从前一状态转移到后一状态