LeetCode:123.買賣股票的最佳時(shí)機(jī)III

123. 買賣股票的最佳時(shí)機(jī) III - 力扣（LeetCode）

1.思路

將兩次買入賣出轉(zhuǎn)化為是否持有的狀態(tài)，當(dāng)天可進(jìn)行兩次買賣，故每天買賣有四種狀態(tài)，四種狀態(tài)包含了當(dāng)天不買不賣的狀態(tài)。

2.代碼實(shí)現(xiàn)

 1class?Solution?{
 2????public?int?maxProfit(int[]?prices)?{
 3
 4????????//?根據(jù)買入賣出定義多種狀態(tài)：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.復(fù)雜度分析

時(shí)間復(fù)雜度：O(n).
空間復(fù)雜度：O(1).

LeetCode:188.買賣股票的最佳時(shí)機(jī)IV?

188. 買賣股票的最佳時(shí)機(jī) IV - 力扣（LeetCode）

1.思路

在上一題的基礎(chǔ)上，將第i天是否持有股票或不持有和第幾次持有或不持有股票作為一個(gè)循環(huán)體進(jìn)行i天，每天k次的循環(huán)遍歷，最終輸出結(jié)果即可。

2.代碼實(shí)現(xiàn)

 1class?Solution?{
 2????public?int?maxProfit(int?k,?int[]?prices)?{
 3
 4????????//?定義dp[][][]?數(shù)組，[天數(shù)][交易次數(shù)][是否持有股票]
 5????????int?len?=?prices.length;
 6????????int[][][]?dp?=?new?int[len][k?+?1][2];
 7
 8????????//?初始化dp數(shù)組
 9????????//?初始化所有的交易次數(shù)是為確保?最后結(jié)果是最多?k?次買賣的最大利潤(rùn)
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.復(fù)雜度分析

時(shí)間復(fù)雜度：O(nk). 空間復(fù)雜度：O(nk).文章來源地址http://www.zghlxwxcb.cn/news/detail-656467.html

到了這里，關(guān)于算法練習(xí)Day50|● 123.買賣股票的最佳時(shí)機(jī)III ● 188.買賣股票的最佳時(shí)機(jī)IV的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！