1、題目：

給你一個(gè)整數(shù)數(shù)組 prices，其中 prices[i] 表示某支股票第 i 天的價(jià)格。
在每一天，你可以決定是否購(gòu)買和/或出售股票。你在任何時(shí)候最多只能持一股股票。你也可以先購(gòu)買，然后在同一天出售。
返回你能獲得的最大利潤(rùn) 。

2、分析特點(diǎn)：

• 題目要求：在任何時(shí)候最多只能持一股股票 ==> 考慮到「不能同時(shí)參與多筆交易」，因此每天交易結(jié)束后只可能存在手里 有一支股票或者沒有股票的狀態(tài) 。
• 有和沒有股票的狀態(tài) ==> 動(dòng)態(tài)規(guī)劃

定義狀態(tài)dp[0] 表示第天交易完后手里沒有股票的最大利潤(rùn)，d[1] 表示第天交易完后手里持有一支股票的最大利潤(rùn)(從0開始)。

考慮dp[i][0] 的轉(zhuǎn)移方程，如果這一天交易完后手里沒有股票，那么可能的轉(zhuǎn)移狀態(tài)為前一天已經(jīng)沒有股票，即 dp[i-1][0]，
或者前一天結(jié)束的時(shí)候手里持有一支股票，即 dp[i-1][1]，這時(shí)候我們要將其賣出，并獲得 prices[i] 的收益。
因此為了收益最大化，我們列出如下的轉(zhuǎn)移方程:

再來(lái)考慮dp[i][1]，按照同樣的方式考慮轉(zhuǎn)移狀態(tài)，那么可能的轉(zhuǎn)移狀態(tài)為前一天已經(jīng)持有一支股票，即 dp[i-1][1]，或者前一天結(jié)束時(shí)還沒有股票，即 dp[i-1][0]，這時(shí)候我們要將其買入，并減少prices[i]的收益。可以列出如下的轉(zhuǎn)移方程:

對(duì)于初始狀態(tài)，根據(jù)狀態(tài)定義我們可以知道第0天交易結(jié)束的時(shí)候 dp[0][0] =0，dp[0][1]=-prices0。
因此，我們只要從前往后依次計(jì)算狀態(tài)即可。由于全部交易結(jié)束后，持有股票的收益一定低于不持有股票的收益，因此這時(shí)候 dp[n-1][0] 的收益必然是大于 dp[n-1][0] 的，最后的答案即為dp[n-1][0]。

3、特點(diǎn)：

本題動(dòng)態(tài)規(guī)劃法的思路解析：

因?yàn)?，從最后一天往前看，分成四種情況：

A：前一天有股票，并賣出 – 剩余股票數(shù)0

B：前一天沒有股票，并不買入 – 剩余股票數(shù)0

C：前一天有股票，并不買出 – 剩余股票數(shù)1

D：前一天沒有股票，并買入 – 剩余股票數(shù)1

所以：

• 當(dāng)剩余股票數(shù)0時(shí)，最大的利潤(rùn)是max(A, B)
• 當(dāng)剩余股票數(shù)1時(shí)，最大的利潤(rùn)是max(C, D)

4、代碼：

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];
    }
}

注意到上面的狀態(tài)轉(zhuǎn)移方程中，每一天的狀態(tài)只與前一天的狀態(tài)有關(guān)，而與更早的狀態(tài)都無(wú)關(guān)，因此我們不必存儲(chǔ)這些無(wú)關(guān)的狀態(tài)，只需要將 dp[i-1][0]和dp[i-1][0] 存放在兩個(gè)變量中，通過(guò)它們計(jì)算出dp[i][0] 和 dp[i][1] 并存回對(duì)應(yīng)的變量，以便于第 i+1 天的狀態(tài)轉(zhuǎn)移即可。

4、復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n)，其中 nnn 為數(shù)組的長(zhǎng)度。一共有 2n 個(gè)狀態(tài)，每次狀態(tài)轉(zhuǎn)移的時(shí)間復(fù)雜度為 O(1)，因此時(shí)間復(fù)雜度為 O(2n)=O(n)。
• 空間復(fù)雜度：O(n)。我們需要開辟 O(n) 空間存儲(chǔ)動(dòng)態(tài)規(guī)劃中的所有狀態(tài)。如果使用空間優(yōu)化，空間復(fù)雜度可以優(yōu)化至 O(1)。

5、總結(jié)：

本題動(dòng)態(tài)規(guī)劃法的思路解析---有股票和沒股票結(jié)合買入賣出的情況考慮狀態(tài)

因?yàn)?，從最后一天往前看，分成四種情況：

A：前一天有股票，并賣出 – 剩余股票數(shù)0

B：前一天沒有股票，并不買入 – 剩余股票數(shù)0

C：前一天有股票，并不買出 – 剩余股票數(shù)1

D：前一天沒有股票，并買入 – 剩余股票數(shù)1

所以：

• 當(dāng)剩余股票數(shù)0時(shí)，最大的利潤(rùn)是max(A, B)
• 當(dāng)剩余股票數(shù)1時(shí)，最大的利潤(rùn)是max(C, D)

如果本文對(duì)你有幫助的話記得給一樂(lè)點(diǎn)個(gè)贊哦，感謝！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-708618.html

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