??思維導圖整理大廠面試高頻陣列17: 股票問題I的通用dp陣列定義法 和 貪心法思想, 力扣121??

此專欄文章是對力扣上演算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.

目的是為了更方便快捷的記憶和回憶演算法重點(不用每次都重復看題解), 畢竟演算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容).

關于本專欄所有題目的目錄鏈接, 刷演算法題目的順序/注意點/技巧, 以及思維導圖源檔案問題請點擊此鏈接.

想進大廠, 刷演算法是必不可少的, 歡迎和博主一起打卡刷力扣演算法, 博主同步更新了演算法視頻講解 和 其他文章/導圖講解, 更易于理解, 歡迎來看!

關注博主獲得題解更新的最新訊息!!!

文章目錄

• • 0.導圖整理
  • 1.動態規劃的不同定義法
  • 2.貪心法的思想
  • 原始碼
  • • Python:
    • java:

題目鏈接: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/si-wei-dao-tu-zheng-li-tong-yong-dpshu-z-n6n8/

0.導圖整理

1.動態規劃的不同定義法

這是股票系列問題的第一題, 題目本身難度也并不是太大, 可能很多人第一次看到這個問題并不會直接想到用動態規劃來解決, 因為它確實也有很多其他簡單的方法來解決, 比如下面要介紹的貪心法等.

這題用動態規劃來求解, 確實有點大材小用的感覺, 但是這里還是詳細的介紹一下, 因為這種動態規劃的思想對于股票系列的后面幾題幾乎都是通用的思想, 現在掌握了這個思想, 之后幾題處理起來就比較容易了.

當然, 大家在看題解的時候, 可能會看到好幾種dp陣列的定義方法, 有些題解只定義了一個一維dp陣列也能解決此題, 那種比較特殊的情況我們就不討論了, 這里介紹下大家最常看到的dp陣列定義方法: dp[i][0],dp[i][1]來定義第i天持有/不持有股票所得的最多現金.

這里說下我的定義方法, 在之前的 最長湍流子陣列 中也已經提及了這種方式, 就是我們定義dp陣列時最好采用一些能直接看出含義的名稱, 比如之前定義的up[i]和down[i], 大家看到后一下子就能明白dp陣列的含義, 而不用反復的去看自己之前的定義. 另外一個好處就是: 這種方法可以將二維dp陣列直接優化為一維dp陣列, 還能節省空間, 所以推薦大家在可能的情況下都采用這種定義方式.

所以本題我采用的定義方式是: have[i] 表示第i天持有股票所得最多現金, no[i] 表示第i天不持有股票所得最多現金, 這種定義方式是不是一目了然, 比使用二維dp陣列好多了!

這里有個特別重要的注意點, 一定要搞清楚持有的概念, 在之后的系列題目中我們都會用到這個概念: “持有”不代表就是當天“買入”！也有可能是昨天或更早就買入了, 今天保持持有的狀態!

定義好dp陣列后, 就是推導遞推公式了, 本題的難點在于每個狀態都是由兩種情況組合而成的, 最后我們要選擇其中的最大值:

這里可能有人會疑惑 持有股票的現金, 其實一開始現金是0, 那么加入第i天買入股票現金就是 -prices[i], 這是一個負數.

最后就是 dp陣列如何初始化問題了, 這個也不難理解:

都定義結束后, 就可以撰寫出未優化的代碼了, 之后就可以對代碼進行空間優化了. 優化的技巧在大多數時候都是直接將dp陣列用變數來替換一下就可以了, 大家可以先替換下看看程式能不能運行通過, 不能通過的話就是特殊情況了, 我們就要好好考慮如何優化了. 原理也是很簡單的, 因為當前狀態只和上一個狀態有關, 因此我們只需要用一個變數來記錄上一個狀態的值就可以了!

2.貪心法的思想

上面提到了, 本題比較容易, 也有很多更簡單的方法來解決, 貪心法就是其中一個. 因為股票就買賣一次, 那么貪心的想法很自然就是取最左最小值, 取最右最大值, 那么得到的差值就是最大利潤.

這里要注意 最左最小值: 它是指當前天 之前的最小值, 相當于區域最小值, 并不是全域最小值, 官方題解中稱為 歷史最低點, 其實都是表達的同一個意思, 但不少人可能將 歷史最低點 理解為 全域最低點, 感覺官方題解有問題, 其實是沒有問題的! 具體實作也不難, 可查看相關代碼!

原始碼

Python:

# 動態規劃
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)
        if len == 0:
            return 0
        have = [0] * length  # 表示第i天持有股票所得最多現金
        no = [0] * length    # 表示第i天不持有股票所得最多現金
        have[0] = -prices[0] # 此時的持有股票就一定是買入股票了
        no[0] = 0            # 不持有股票那么現金就是0
        for i in range(1, length):
            have[i] = max(have[i-1], -prices[i])
            no[i] = max(no[i-1], prices[i] + have[i-1])
        return no[-1]  # 不持有股票狀態所得金錢一定比持有股票狀態得到的多
        
# 空間優化
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)
        if len == 0:
            return 0
        have = -prices[0] # 此時的持有股票就一定是買入股票了
        no = 0            # 不持有股票那么現金就是0
        for i in range(1, length):
            have = max(have, -prices[i])
            no = max(no, prices[i] + have)
        return no  # 不持有股票狀態所得金錢一定比持有股票狀態得到的多

# 貪心法
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        low = float("inf")
        result = 0
        for i in range(len(prices)):
            low = min(low, prices[i]) # 取最左最小價格
            result = max(result, prices[i] - low) # 直接取最大區間利潤
        return result

java:

// 動態規劃
public class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }
        int[] have = new int[len];  // 表示第i天持有股票所得最多現金
        int[] no = new int[len];    // 表示第i天不持有股票所得最多現金
        have[0] = -prices[0]; // 此時的持有股票就一定是買入股票了
        no[0] = 0;            // 不持有股票那么現金就是0

        for (int i = 1; i < len; i++) {
            have[i] = Math.max(have[i-1], -prices[i]);
            no[i] = Math.max(no[i-1], prices[i] + have[i-1]);
        }
        return no[len - 1];
    }
}

// 貪心法
class Solution {
    public int maxProfit(int[] prices) {
        int low = Integer.MAX_VALUE;
        int result = 0;
        for (int i = 0; i < prices.length; i++) {
            low = Math.min(low, prices[i]);  // 取最左最小價格
            result = Math.max(result, prices[i] - low); // 直接取最大區間利潤
        }
        return result;
    }
}

我的更多精彩文章鏈接, 歡迎查看

各種電腦/軟體/生活/音樂/動漫/電影技巧匯總(你肯定能夠找到你需要的使用技巧)

力扣演算法刷題 根據思維導圖整理筆記快速記憶演算法重點內容(歡迎和博主一起打卡刷題哦)

計算機專業知識 思維導圖整理

最值得收藏的 Python 全部知識點思維導圖整理, 附帶常用代碼/方法/庫/資料結構/常見錯誤/經典思想(持續更新中)

最值得收藏的 C++ 全部知識點思維導圖整理(清華大學鄭莉版), 東南大學軟體工程初試906科目

最值得收藏的 計算機網路 全部知識點思維導圖整理(王道考研), 附帶經典5層結構中英對照和框架簡介

最值得收藏的 演算法分析與設計 全部知識點思維導圖整理(北大慕課課程)

最值得收藏的 資料結構 全部知識點思維導圖整理(王道考研), 附帶經典題型整理

最值得收藏的 人工智能導論 全部知識點思維導圖整理(王萬良慕課課程)

最值得收藏的 數值分析 全部知識點思維導圖整理(東北大學慕課課程)

最值得收藏的 數字影像處理 全部知識點思維導圖整理(武漢大學慕課課程)

紅黑樹 一張導圖解決紅黑樹全部插入和洗掉問題 包含詳細操作原理 情況對比

各種常見排序演算法的時間/空間復雜度 是否穩定 演算法選取的情況 改進 思維導圖整理

人工智能課件 演算法分析課件 Python課件 數值分析課件 機器學習課件 影像處理課件

考研相關科目 知識點 思維導圖整理

考研經驗–東南大學軟體學院軟體工程(這些基礎課和專業課的各種坑和復習技巧你應該知道)

東南大學 軟體工程 906 資料結構 C++ 歷年真題 思維導圖整理

東南大學 軟體工程 復試3門科目歷年真題 思維導圖整理

最值得收藏的 考研高等數學 全部知識點思維導圖整理(張宇, 湯家鳳), 附做題技巧/易錯點/知識點整理

最值得收藏的 考研線性代數 全部知識點思維導圖整理(張宇, 湯家鳳), 附帶慣用思維/做題技巧/易錯點整理

高等數學 中值定理 一張思維導圖解決中值定理所有題型

考研思修 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理

考研近代史 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理

考研馬原 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理

考研數學課程筆記 考研英語課程筆記 考研英語單詞詞根詞綴記憶 考研政治課程筆記

Python相關技術 知識點 思維導圖整理

Numpy常見用法全部OneNote筆記 全部筆記思維導圖整理

Pandas常見用法全部OneNote筆記 全部筆記思維導圖整理

Matplotlib常見用法全部OneNote筆記 全部筆記思維導圖整理

PyTorch常見用法全部OneNote筆記 全部筆記思維導圖整理

Scikit-Learn常見用法全部OneNote筆記 全部筆記思維導圖整理

Java相關技術/ssm框架全部筆記

Spring springmvc Mybatis jsp

科技相關 小米手機

小米 紅米 歷代手機型號大全 發布時間 發布價格

常見手機品牌的各種系列劃分及其特點

歷代CPU和GPU的性能情況和常見后綴的含義 思維導圖整理