<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??一站式輕松地調用各大LLM模型接口,支持GPT4、智譜、豆包、星火、月之暗面及文生圖、文生視頻 廣告
                # 0309. 最佳買賣股票時機含冷凍期 ## 題目地址(309. 最佳買賣股票時機含冷凍期) <https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個整數數組,其中第 i 個元素代表了第 i 天的股票價格 。 設計一個算法計算出最大利潤。在滿足以下約束條件下,你可以盡可能地完成更多的交易(多次買賣一支股票): 你不能同時參與多筆交易(你必須在再次購買前出售掉之前的股票)。 賣出股票后,你無法在第二天買入股票 (即冷凍期為 1 天)。 示例: 輸入: [1,2,3,0,2] 輸出: 3 解釋: 對應的交易狀態為: [買入, 賣出, 冷凍期, 買入, 賣出] ``` ``` ## 前置知識 - [動態規劃](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md) ## 公司 - 阿里 - 騰訊 - 字節 ## 思路 這是一道典型的 DP 問題, DP 問題的核心是找到狀態和狀態轉移方程。 這道題目的狀態似乎比我們常見的那種 DP 問題要多,這里的狀態有 buy sell cooldown 三種, 我們可以用三個數組來表示這這三個狀態,buy,sell, cooldown. - buy\[i\]表示第 i 天,且以 buy 結尾的最大利潤 - sell\[i\]表示第 i 天,且以 sell 結尾的最大利潤 - cooldown\[i\]表示第 i 天,且以 sell 結尾的最大利潤 我們思考一下,其實 cooldown 這個狀態數組似乎沒有什么用,因此 cooldown 不會對`profit`產生 任何影響。 我們可以進一步縮小為兩種狀態。 - buy\[i\] 表示第 i 天,且以 buy 或者 coolwown 結尾的最大利潤 - sell\[i\] 表示第 i 天,且以 sell 或者 cooldown 結尾的最大利潤 對應的狀態轉移方程如下: > 這個需要花點時間來理解 ``` <pre class="calibre18">``` buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]); sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]); ``` ``` 我們來分析一下,buy\[i\]對應第 i 的 action 只能是 buy 或者 cooldown。 - 如果是 cooldown,那么 profit 就是 buy\[i - 1\] - 如果是 buy,那么就是`前一個賣的profit減去今天買股票花的錢`,即 sell\[i -2\] - prices\[i\] > 注意這里是 i - 2,不是 i-1 ,因為有 cooldown 的限制 sell\[i\]對應第 i 的 action 只能是 sell 或者 cooldown。 - 如果是 cooldown,那么 profit 就是 sell\[i - 1\] - 如果是 sell,那么就是`前一次買的時候獲取的利潤加上這次賣的錢`,即 buy\[i - 1\] + prices\[i\] ## 關鍵點解析 - 多狀態動態規劃 ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=309 lang=javascript * * [309] Best Time to Buy and Sell Stock with Cooldown * */</span> <span class="hljs-title">/** * @param {number[]} prices * @return {number} */</span> <span class="hljs-keyword">var</span> maxProfit = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">prices</span>) </span>{ <span class="hljs-keyword">if</span> (prices == <span class="hljs-params">null</span> || prices.length <= <span class="hljs-params">1</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-title">// 定義狀態變量</span> <span class="hljs-keyword">const</span> buy = []; <span class="hljs-keyword">const</span> sell = []; <span class="hljs-title">// 尋常</span> buy[<span class="hljs-params">0</span>] = -prices[<span class="hljs-params">0</span>]; buy[<span class="hljs-params">1</span>] = <span class="hljs-params">Math</span>.max(-prices[<span class="hljs-params">0</span>], -prices[<span class="hljs-params">1</span>]); sell[<span class="hljs-params">0</span>] = <span class="hljs-params">0</span>; sell[<span class="hljs-params">1</span>] = <span class="hljs-params">Math</span>.max(<span class="hljs-params">0</span>, prices[<span class="hljs-params">1</span>] - prices[<span class="hljs-params">0</span>]); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">2</span>; i < prices.length; i++) { <span class="hljs-title">// 狀態轉移方程</span> <span class="hljs-title">// 第i天只能是買或者cooldown</span> <span class="hljs-title">// 如果買利潤就是sell[i - 2] - prices[i], 注意這里是i - 2,不是 i-1 ,因為有cooldown的限制</span> <span class="hljs-title">// cooldown就是buy[i -1]</span> buy[i] = <span class="hljs-params">Math</span>.max(buy[i - <span class="hljs-params">1</span>], sell[i - <span class="hljs-params">2</span>] - prices[i]); <span class="hljs-title">// 第i天只能是賣或者cooldown</span> <span class="hljs-title">// 如果賣利潤就是buy[i -1] + prices[i]</span> <span class="hljs-title">// cooldown就是sell[i -1]</span> sell[i] = <span class="hljs-params">Math</span>.max(sell[i - <span class="hljs-params">1</span>], buy[i - <span class="hljs-params">1</span>] + prices[i]); } <span class="hljs-keyword">return</span> <span class="hljs-params">Math</span>.max(buy[prices.length - <span class="hljs-params">1</span>], sell[prices.length - <span class="hljs-params">1</span>], <span class="hljs-params">0</span>); }; ``` ``` ## 相關題目 - [121.best-time-to-buy-and-sell-stock](121.best-time-to-buy-and-sell-stock.html) - [122.best-time-to-buy-and-sell-stock-ii](122.best-time-to-buy-and-sell-stock-ii.html)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看