LeetCode:123.買賣股票的最佳時機III

123. 買賣股票的最佳時機 III - 力扣（LeetCode）

1.思路

將兩次買入賣出轉化為是否持有的狀態，當天可進行兩次買賣，故每天買賣有四種狀態，四種狀態包含了當天不買不賣的狀態。

2.代碼實現

 1class?Solution?{2????public?int?maxProfit(int[]?prices)?{34????????//?根據買入賣出定義多種狀態：0表示不操作，1表示第一次持有，2表示第一次不持有，3表示第二次持有，4表示第2次不持有5????????int[][]?dp?=?new?int[prices.length][5];6????????dp[0][0]?=?0;7????????dp[0][1]?=?-prices[0];8????????dp[0][2]?=?0;9????????dp[0][3]?=?-prices[0];
10????????dp[0][4]?=?0;
11
12????????for?(int?i?=?1;?i?<?prices.length;?i++)?{
13????????????//?第一次持有，前一天就持有?或?第i天買入持有
14????????????dp[i][1]?=?Math.max(dp[i?-?1][1],?-prices[i]);
15????????????//?第一次不持有，前一天不持有?或?第i天不持有
16????????????dp[i][2]?=?Math.max(dp[i?-?1][2],?dp[i?-?1][1]?+?prices[i]);
17????????????//?第二次持有，前一天第二次持有?或?前一天不持有第i天持有
18????????????dp[i][3]?=?Math.max(dp[i?-?1][3],?dp[i?-?1][2]?-?prices[i]);
19????????????//?第二次不持有，前一天第二次不持有?或前一天第二次持有第i天賣出
20????????????dp[i][4]?=?Math.max(dp[i?-?1][4],?dp[i?-?1][3]?+?prices[i]);
21????????}
22????????return?Math.max(dp[prices.length?-?1][2],?dp[prices.length?-?1][4]);
23????}
24}
25

3.復雜度分析

時間復雜度：O(n).
空間復雜度：O(1).

LeetCode:188.買賣股票的最佳時機IV?

188. 買賣股票的最佳時機 IV - 力扣（LeetCode）

1.思路

在上一題的基礎上，將第i天是否持有股票或不持有和第幾次持有或不持有股票作為一個循環體進行i天，每天k次的循環遍歷，最終輸出結果即可。

2.代碼實現

 1class?Solution?{2????public?int?maxProfit(int?k,?int[]?prices)?{34????????//?定義dp[][][]?數組，[天數][交易次數][是否持有股票]5????????int?len?=?prices.length;6????????int[][][]?dp?=?new?int[len][k?+?1][2];78????????//?初始化dp數組9????????//?初始化所有的交易次數是為確保?最后結果是最多?k?次買賣的最大利潤
10????????for?(int?i?=?0;?i?<=?k;?i++)?{
11????????????dp[0][i][1]?=?-prices[0];
12????????}
13
14????????for?(int?i?=?1;?i?<?len;?i++)?{
15????????????for?(int?j?=?1;?j?<=?k;?j++)?{
16????????????????//?0?表示不持有股票
17????????????????//?1?表示持有股票
18????????????????dp[i][j][0]?=?Math.max(dp[i?-?1][j][0],?dp[i?-?1][j][1]?+?prices[i]);
19????????????????dp[i][j][1]?=?Math.max(dp[i?-?1][j][1],?dp[i?-?1][j?-?1][0]?-?prices[i]);
20????????????}
21????????}
22????????return?dp[len?-?1][k][0];
23????}
24}
25

3.復雜度分析

時間復雜度：O(nk). 空間復雜度：O(nk).