JavaScript股票的動態買賣規劃實例分析

本文小編為大家詳細介紹“JavaScript股票的動態買賣規劃實例分析”，內容詳細，步驟清晰，細節處理妥當，希望這篇“JavaScript股票的動態買賣規劃實例分析”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

1. 最佳買賣股票時機含冷凍期

題目描述

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

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

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

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

示例 1:

輸入: prices = [1,2,3,0,2]
輸出: 3 
解釋: 對應的交易狀態為: [買入, 賣出, 冷凍期, 買入, 賣出]

示例 2:

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

力扣鏈接

題解

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

• 我們目前持有一支股票，對應的 累計最大收益 記為 dp[i][0]；

• 我們目前不持有任何股票，并且處于冷凍期中，對應的 累計最大收益 記為 f[i][1]；

• 我們目前不持有任何股票，并且不處于冷凍期中，對應的 累計最大收益 記為 f[i][2]。

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

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

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

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

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

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

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

/**
 * @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. 買賣股票的最佳時機 III

題目描述

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

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

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

示例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

力扣鏈接

題解

每一天結束之后，有可能處于以下五種狀態之一：

1. 沒有買股也沒有賣股。

2. 買了第一支股，但是還沒有賣出第一支股。

3. 買了第一支股，并且賣出第一支股。

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

5. 買了第一支股，并且賣出第一支股，買了第二支股，并且賣出第二支股。

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

• 對于第一種情況，利潤始終為 0。

• 對于第二種情況，由于還沒有盈利，只買進了某支股，為虧損狀態。此時，虧損的最小值是 prices[0] 至 prices[i] 的最小值，假設為 buy1。可以看做，第二種情況利潤的最大值為：-buy1。狀態轉移方程為：buy1 = max(buy1, -prices[i]);

• 對于第三種情況，利潤的計算需要在第二種情況的基礎上再賣出一支股。所以需要先計算第二種情況，再在遍歷到 prices[i] 的時候，判斷要不要賣出。如果在以最小的虧損買入第一支股的情況下，賣出當前這支股所得利潤最大，則賣出當前這支股。狀態轉移方程為：sell1 = max(sell1, prices[i] + buy1); 注意這里是 prices[i] + buy1，不是 prices[i] - buy1，因為 buy1 是負值，代表利潤。

• 對于第四種情況，不能直接買入，因為有可能第一支股還沒賣出。利潤的計算需要在第三種情況的基礎上再買入一支股。所以需要先計算第三種情況，再在遍歷到 prices[i] 的時候，判斷要不要買入。如果在賣出第一支股所得利潤最大的情況下，買入當前這支股最終所得利潤最大，則買入當前這支股。狀態轉移方程為：buy2 = max(buy2, sell1 - prices[i]);

• 對于第五種情況，利潤的計算需要在第四種情況的基礎上再賣出一支股。所以需要先計算第四種情況，再在遍歷到 prices[i] 的時候，判斷要不要賣出。如果在賣出第一支股然后買入第二支股所得利潤最大的情況下，賣出當前這支股所得利潤最大，則賣出當前這支股。狀態轉移方程為：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;
};

讀到這里，這篇“JavaScript股票的動態買賣規劃實例分析”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。