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

Posted on by

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股票的動態買賣規劃實例分析下篇的文章就介紹到這瞭,更多相關JS股票內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：