1. 最佳買賣股票時機(jī)含冷凍期

題目描述

給定一個整數(shù)數(shù)組prices，其中第prices[i]表示第i天的股票價格 。

設(shè)計一個算法計算出最大利潤。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:

賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例 1:

輸入: prices = [1,2,3,0,2]
輸出: 3 
解釋: 對應(yīng)的交易狀態(tài)為: [買入, 賣出, 冷凍期, 買入, 賣出]

示例 2:

輸入: prices = [1]
輸出: 0

力扣鏈接

題解

我們用 dp[i] 表示第 i 天結(jié)束之后的「累計最大收益」。根據(jù)題目描述，由于我們最多只能同時買入（持有）一支股票，并且賣出股票后有冷凍期的限制，因此我們會有三種不同的狀態(tài)：

• 我們目前持有一支股票，對應(yīng)的 累計最大收益 記為 dp[i][0]；
• 我們目前不持有任何股票，并且處于冷凍期中，對應(yīng)的 累計最大收益 記為 f[i][1]；
• 我們目前不持有任何股票，并且不處于冷凍期中，對應(yīng)的 累計最大收益 記為 f[i][2]。

如何進(jìn)行狀態(tài)轉(zhuǎn)移呢？在第 i 天時，我們可以在不違反規(guī)則的前提下進(jìn)行 買入 或者 賣出 操作，此時第 i 天的狀態(tài)會從第 i−1 天的狀態(tài)轉(zhuǎn)移而來；我們也可以不進(jìn)行任何操作，此時第 i 天的狀態(tài)就等同于第 i−1 天的狀態(tài)。那么我們分別對這三種狀態(tài)進(jìn)行分析：

對于 dp[i][0]，我們目前持有的這一支股票可以是在第 i−1 天就已經(jīng)持有的，對應(yīng)的狀態(tài)為 f[i−1][0]；或者是第 i 天買入的，那么第 i-1 天就不能持有股票并且不處于冷凍期中，對應(yīng)的狀態(tài)為 dp[i−1][2] 加上買入股票的負(fù)收益 prices[i]。因此狀態(tài)轉(zhuǎn)移方程為：dp[i][0]=max(dp[i−1][0], dp[i−1][2]−prices[i])

對于 dp[i][1]，我們在第 i 天結(jié)束之后處于冷凍期的原因是在當(dāng)天賣出了股票，那么說明在第 i−1 天時我們必須持有一支股票，對應(yīng)的狀態(tài)為 dp[i−1][0] 加上賣出股票的正收益 prices[i]。因此狀態(tài)轉(zhuǎn)移方程為：dp[i][1]=dp[i−1][0]+prices[i]

對于 dp[i][2]，我們在第 i 天結(jié)束之后不持有任何股票并且不處于冷凍期，說明當(dāng)天沒有進(jìn)行任何操作，即第 i-1 天時不持有任何股票：如果處于冷凍期，對應(yīng)的狀態(tài)為 dp[i−1][1]；如果不處于冷凍期，對應(yīng)的狀態(tài)為 dp[i−1][2]。因此狀態(tài)轉(zhuǎn)移方程為：dp[i][2]=max(dp[i−1][1],dp[i−1][2])

這樣我們就得到了所有的狀態(tài)轉(zhuǎn)移方程。如果一共有 n 天，那么最終的答案即為：max(dp[n−1][0],dp[n−1][1],dp[n−1][2])

注意到如果在最后一天（第 n−1 天）結(jié)束之后，手上仍然持有股票，那么顯然是沒有任何意義的。因此更加精確地，最終的答案實際上是 dp[n-1][1] 和 dp[n-1][2] 中的較大值，即：max(dp[n−1][1],dp[n−1][2])

注意到上面的狀態(tài)轉(zhuǎn)移方程中，dp[i][..] 只與 dp[i-1][..] 有關(guān)，而與 dp[i-2][..] 及之前的所有狀態(tài)都無關(guān)，因此我們不必存儲這些無關(guān)的狀態(tài)。也就是說，我們只需要將 dp[i-1][0]，dp[i−1][1]，dp[i-1][2] 存放在三個變量中，通過它們計算出 dp[i][0]，dp[i][1]，dp[i][2] 并存回對應(yīng)的變量，以便于第 i+1 天的狀態(tài)轉(zhuǎn)移即可。

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
  const length = prices.length;
  let [dp0, dp1, dp2] = [-prices[0], 0, 0];
  for(let i = 1; i < length; i++) {
    let newDp0 = Math.max(dp0, dp1 - prices[i]);
    let newDp1 = Math.max(dp1, dp2);
    let newDp2 = dp0 + prices[i];
    dp0 = newDp0;
    dp1 = newDp1;
    dp2 = newDp2;
  }
  return Math.max(dp1, dp2);
};

2. 買賣股票的最佳時機(jī) III

題目描述

給定一個數(shù)組，它的第 i 個元素是一支給定的股票在第 i 天的價格。

設(shè)計一個算法來計算你所能獲取的最大利潤。你最多可以完成兩筆交易。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例1:

輸入：prices = [3,3,5,0,0,3,1,4]
輸出：6
解釋：在第 4 天（股票價格 = 0）的時候買入，在第 6 天（股票價格 = 3）的時候賣出，這筆交易所能獲得利潤 = 3-0 = 3 。
     隨后，在第 7 天（股票價格 = 1）的時候買入，在第 8 天 （股票價格 = 4）的時候賣出，這筆交易所能獲得利潤 = 4-1 = 3 。

示例 2：

輸入：prices = [1,2,3,4,5]
輸出：4
解釋：在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接連購買股票，之后再將它們賣出。   
     因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。

示例 3：

輸入：prices = [7,6,4,3,1] 
輸出：0 
解釋：在這個情況下, 沒有交易完成, 所以最大利潤為 0。

示例 4：

輸入：prices = [1]
輸出：0

力扣鏈接

題解

每一天結(jié)束之后，有可能處于以下五種狀態(tài)之一：

1. 沒有買股也沒有賣股。
2. 買了第一支股，但是還沒有賣出第一支股。
3. 買了第一支股，并且賣出第一支股。
4. 買了第一支股，并且賣出第一支股，買了第二支股，但是還沒有賣出第二支股。
5. 買了第一支股，并且賣出第一支股，買了第二支股，并且賣出第二支股。

我們可以遍歷 prices 數(shù)組，模擬第 i 天的情況。計算出第 i 天五種情況利潤的最大值。

• 對于第一種情況，利潤始終為 0。
• 對于第二種情況，由于還沒有盈利，只買進(jìn)了某支股，為虧損狀態(tài)。此時，虧損的最小值是 prices[0] 至 prices[i] 的最小值，假設(shè)為 buy1。可以看做，第二種情況利潤的最大值為：-buy1。狀態(tài)轉(zhuǎn)移方程為：buy1 = max(buy1, -prices[i]);
• 對于第三種情況，利潤的計算需要在第二種情況的基礎(chǔ)上再賣出一支股。所以需要先計算第二種情況，再在遍歷到 prices[i] 的時候，判斷要不要賣出。如果在以最小的虧損買入第一支股的情況下，賣出當(dāng)前這支股所得利潤最大，則賣出當(dāng)前這支股。狀態(tài)轉(zhuǎn)移方程為：sell1 = max(sell1, prices[i] + buy1); 注意這里是 prices[i] + buy1，不是 prices[i] - buy1，因為 buy1 是負(fù)值，代表利潤。
• 對于第四種情況，不能直接買入，因為有可能第一支股還沒賣出。利潤的計算需要在第三種情況的基礎(chǔ)上再買入一支股。所以需要先計算第三種情況，再在遍歷到 prices[i] 的時候，判斷要不要買入。如果在賣出第一支股所得利潤最大的情況下，買入當(dāng)前這支股最終所得利潤最大，則買入當(dāng)前這支股。狀態(tài)轉(zhuǎn)移方程為：buy2 = max(buy2, sell1 - prices[i]);
• 對于第五種情況，利潤的計算需要在第四種情況的基礎(chǔ)上再賣出一支股。所以需要先計算第四種情況，再在遍歷到 prices[i] 的時候，判斷要不要賣出。如果在賣出第一支股然后買入第二支股所得利潤最大的情況下，賣出當(dāng)前這支股所得利潤最大，則賣出當(dāng)前這支股。狀態(tài)轉(zhuǎn)移方程為：sell2 = max(sell2, prices[i] + buy2);

最終的 sell2 就是我們要的答案。

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  const n = prices.length;
  let buy1 = -prices[0];
  let sell1 = 0;
  let buy2 = -prices[0];
  let sell2 = 0;
  for (let i = 1; i < n; i++) {
    buy1 = Math.max(buy1, -prices[i]);
    sell1 = Math.max(sell1, prices[i] + buy1);
    buy2 = Math.max(buy2, sell1 - prices[i]);
    sell2 = Math.max(sell2, prices[i] + buy2);
  }
  return sell2;
};

到此這篇關(guān)于JavaScript股票的動態(tài)買賣規(guī)劃實例分析下篇的文章就介紹到這了,更多相關(guān)JS股票內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論