• 前言知識
• 第一章，算法簡介
  • 1.2，二分法查找元素
    • 1.2.1，特殊的二分查找
• 第二章，選擇排序
  • 2.1，內存工作原理
    • 2.2.1，鏈表
    • 2.2.2，數組
    • 2.2.3，術語
  • 2.3，選擇排序
  • 2.4，小結
• 第三章，遞歸
  • 3.2，基線條件和遞歸條件
  • 3.3，棧
    • 3.3.1，調用棧
    • 3.3.2，遞歸調用棧
  • 3.4，小結
• 第四章，快速排序
  • 4.1，分而治之
  • 4.2 快速排序
  • 4.3 再談大Ｏ表示法
  • 4.4，小結
• 第五章，散列表
  • 5.3，沖突
  • 5.4，性能
  • 5.5，小結
• 第六章，廣度優先搜索
  • 6.1，圖是什么
  • 6.2，廣度優先搜索
  • 6.3，棧與隊列
  • 6.4，代碼實現圖結構
  • 6.4.1 運行時間
• 第七章，迪克斯特拉算法
  • 7.1，使用迪克斯特拉算法
  • 7.2，術語
  • 7.3，負權邊
  • 7.4，編程實現狄克斯特拉算法
  • 7.5，小結
• 第八章，貪婪(貪心)算法
  • 8.1，教室調度問題
  • 8.2，背包問題
  • 8.3，集合覆蓋問題
    • 8.3.1，近似算法
  • 8.4，NP完全問題
    • 8.4.1，如何識別NP完全問題
  • 8.5，小結
• 第九章，動態規劃
  • 9.1，概念
  • 9.2，背包問題
  • 9.1，最長公共子串
• 第十章，K最近鄰算法
• 第十一章　接下來如何做

前言知識

十大經典排序算法動畫與解析，看我就夠了！（配代碼完全版）

10 大排序算法時間復雜度及空間復雜度如下圖：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-A010KZLD-1664372500316)(…/data/images/排序算法時間復雜度.jpg)]

第一章，算法簡介

1.2，二分法查找元素

二分查找是一種算法，其輸入是一個有序的元素列表（必須有序的原因稍后解釋）。如果要查找的元素包含在列表中，二分查找返回其位置；否則返回 null，使用二分查找時，每次猜測的是中間的數字，從而將余下的數字排除一半。（僅僅當列表是有序的時候，二分查找才管用）

一般而言，對于包含n個元素的列表查找某個元素，使用二分法最多需要 $lo{g}_{2}n$ 步(**時間復雜度為 $lo{g}_{2}n$ **)，簡單查找最多需要 n 步。大 O 表示法指出了算法最糟糕情況下的運行時間。二分法實例代碼如下：

def binary_search(list, item):low = 0high = len(list)-1while low <= high:mid = (low + high) // 2if list[mid] == item:return midelif list[mid] > item:high = mid - 1else:low = mid + 1return Noneif __name__ == "__main__":print(binary_search([1,2,3,4,6,7], 3)) # 輸出 2

1.2.1，特殊的二分查找

有序數組中的目標出現多次，利用二分查找返回在最左邊出現的目標值或者是最右邊出現的目標值，實例代碼如下：

def binary_search2(arr, target, flag="left"):if not arr:return Noneleft = 0right = len(arr) - 1while left <= right:mid = left + (right - left) // 2 # 防止數據過大溢出?if arr[mid] < target:left = mid + 1elif arr[mid] > target:right = mid -1else:if flag == "left":if mid > 0 and arr[mid-1] == target:right = mid -1 # 不斷向最左邊逼近else:return midelif flag == "right":if mid + 1 < len(arr) and arr[mid + 1] == target:left = mid + 1 # 不斷向最右邊逼近else:return midreturn Noneif __name__ == "__main__":print(binary_search2([1,1,1,3,3,3,4], 3, "left")) # 查找最左邊出現的目標值, 輸出3print(binary_search2([1,1,1,3,3,3,4,4,4], 3, "right")) # 查找最右邊出現的目標值, 輸出5

第二章，選擇排序

2.1，內存工作原理

在計算機中，存儲多項數據時，有兩種基本方式－數組和鏈表。但它們并非適用于所有情形。

2.2.1，鏈表

鏈表中的元素可存儲在內存的任何地方。
鏈表的每個元素都存儲了下一個元素的地址，從而使一系列隨機的內存地址串在一起。鏈表結構直觀顯示如下圖所示：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-G7hRcnjg-1664372500320)(…/data/images/2.1鏈表.png)]

鏈表的優勢在插入元素方面，那數組的優勢又是什么呢？

2.2.2，數組

需要隨機地讀取元素時，數組的效率很高，因為可迅速找到數組的任何元素。在鏈表中，元素并非靠在一起的，你無法迅速計算出第五個元素的內存 地址，而必須先訪問第一個元素以獲取第二個元素的地址，再訪問第二個元素以獲取第三個元素 的地址，以此類推，直到訪問第五個元素。

2.2.3，術語

數組的元素帶編號，編號從 0 而不是 １ 開始，幾乎所有的編程語言都從０開始對數組元素進行編號，比如C/C++的數組結構和Python的列表結構。
元素的位置稱為索引。下面是常見數組和鏈表操作的運行時間.

2.3，選擇排序

選擇排序時間復雜度$O(n^2)$

def findSmallest(arr):smallest = arr[0] # 存儲最小的值smallest_index = 0 # 存儲最小元素的索引for i in range(1, len(arr)):if arr[i] < smallest:smallest_index = ismallest = arr[i]return smallest # 選擇排序法對數組進行排序 def selectionSort(arr):newArr = []for i in range(len(arr)):smallest = findSmallest(arr)arr.remove(smallest)newArr.append(smallest)return newArr # 實例應用 print(selectionSort([5, 3, 6, 100])) # [3, 5, 6, 100]

2.4，小結

• 計算機內存猶如一大堆抽屜。
• 需要存儲多個元素時，可使用數組或鏈表。
• 數組的元素都在一起。
• 鏈表的元素是分開的，其中每個元素都存儲了下一個元素的地址。
• 數組的讀取速度很快。
• 鏈表的插入和刪除速度很快.
• 在同一個數組中，所有元素的類型都必須相同（都為int、 double等）。

第三章，遞歸

學習如何將問題分成基線條件和遞歸條件，學習如何使用遞歸算法，遞歸算法直觀上更好理解，步驟簡單。

3.2，基線條件和遞歸條件

編寫遞歸函數時，必須告訴它何時停止，因此，每個遞歸函數有兩個部分：基線條件(base case)和遞歸條件(recursive case)。遞歸條件指的是函數調用自己，而基線條件則 指的是函數不再調用自己，從而避免形成無限循環。

3.3，棧

棧的定義：棧是一種只能從表的一端存取數據且遵循 “先進后出” 原則的線性存儲結構。
調用棧(call stack)

3.3.1，調用棧

計算機在內部使用被稱為調用棧的棧。調用另一個函數時，當前函數暫停 并處于未完成狀態。該函數的所有變量的值都還在內存中。棧頂的方框指出了當前執行 到了什么地方。

3.3.2，遞歸調用棧

棧在遞歸中扮演著重要角色。使用棧雖然很方便，但是也要付出代價：存儲詳盡的信息可能占用大量的內存。每個函數調 用都要占用一定的內存，如果棧很高，就意味著計算機存儲了大量函數調用的信息。在這種情況 下，你有兩種選擇。

• 重新編寫代碼
• 使用尾遞歸

3.4，小結

• 遞歸值的是調用自己的函數
• 每個遞歸函數都有兩個條件：基線條件和遞歸條件
• 棧有兩種操作：壓如和彈出
• 所有函數調用都進入調用棧
• 調用棧可能很長，這將占用大量內存

第四章，快速排序

快速排序使用分而治之的策略，分而治之是我們學習的第一種通用的問題解決辦法。
分而治之(divide and conquer，D&C)-一種著名的遞歸式問題解決辦法。

4.1，分而治之

D&C算法是遞歸的。使用D&C解決問題的過程包括兩個步驟：

• 找出基線條件，這種條件必須盡可能簡單。
• 不斷將問題分解（或者說縮小規模），直到符合基線條件。

D&C并非可直接用于解決問題的算法，而是一種解決問題的思路。

4.2 快速排序

C語言標準庫中的函數qsort實現的就是快速排序?？焖倥判蛞彩怯昧薉&C思想。
對數組進行快速排序，步驟如下：

隨機選擇一個基準值；

將數組分成兩個子數組：小于基準值的元素和大于基準值額元素；

對這兩個子數組進行排序。

在平均情況下，快速排序時間復雜度$O(nlogn)$。快速排序代碼如下：

def quicksort(array):if len(array) < 2: # 基線條件：為空或只包含一個元素的數組是“有序”的return arrayelse:# 遞歸條件pivot = array[0] less = [x for x in array[1:] if x <= pivot]greater = [x for x in array[1:] if x > pivot]return quicksort(less) + [pivot] + quicksort(greater) print(quicksort([4, 90, 0, 2, 17, 79, 12])) # [0, 2, 4, 12, 17, 79, 90]

上面的代碼空間復雜度很大，真正的快排是原地排序，空間復雜度為O(1)，代碼如下：

# _*_ coding:utf-8 _*_def quick_sort(L):return q_sort(L, 0, len(L)-1)def q_sort(L, left, right):if left < right:pivot = Partition(L, left, right)q_sort(L, left, pivot-1)q_sort(L, pivot+1, right)return Ldef Partition(L, left, right):pivotkey = L[left]while left < right:while left < right and L[right] >= pivotkey:right -= 1L[left] = L[right]while left < right and L[left] <= pivotkey:left += 1L[right] = L[left] # 遇到比基準大的數, 則覆蓋在之前尾部指針的位置L[left] = pivotkeyreturn leftif __name__ == "__main__":L = [5, 9, 1, 1, 11, 6, 7, 2, 4]print(quick_sort(L))

4.3 再談大Ｏ表示法

快速排序的獨特之處在于，其速度取決于選擇的基準值。在討論快速排序的運行時間前，我 們再來看看最常見的大O運行時間。

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-JYpoxy7V-1664372500324)(…/data/images/4.3再談大O表示法.png)]

• 選擇排序，其運行時間為 $O(n^2)$，速度非常慢。
• 還有一種名為合并排序（merge sort）的排序算法，其運行時間為 $O(nlogn)$，比選擇排序快得多！
• 快速排序的情況比較棘手，在最糟情況下，其運行時間為 $O(n^2)$。與選擇排序一樣慢！但這是最糟情況。在平均情況下，快速排序的運行時間為 $O(nlogn)$。

由對數的換底公式，$lo{g}_{a}n$ 和 $lo{g}_{b}n$ 只有一個常數因子不同，這個因子在大O記法中被丟棄。因此記作$O(logn)$，而不論對數的底是多少，是對數時間算法的標準記法。

4.4，小結

• D&C將問題逐步分解。使用D&C處理列表時，基線條件很可能是空數組或只包含一個元 素的數組。
• 實現快速排序時，請隨機地選擇用作基準值的元素。快速排序的平均運行時間為O(n log n)。
• 大O表示法中的常量有時候事關重大，這就是快速排序比合并排序快的原因所在。
• 比較簡單查找和二分查找時，常量幾乎無關緊要，因為列表很長時， O(log n)的速度比O(n) 快得多。

第五章，散列表

數組和鏈表結構可以用以查找，棧不行。散列表也叫哈希表(Hash table)，散列表有些類似 Python 中的字典 dict 結構。散列表可用以：

• 模擬映射關系；
• 防止重復；
• 緩沖/記住數據，以免服務器再通過處理來生成它們。

5.3，沖突

給兩個鍵分配的位置相同，這被稱為沖突（collision）。處理沖突最簡單的辦法就是：如果兩個鍵映射到了同一個位置，就在這個位置存儲一個鏈表。

5.4，性能

散列表，數組，鏈表的查找、插入刪除元素的時間復雜度，如下表所示：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-mGqZtFSo-1664372500326)(…/images/5.4性能.png)]

在平均情況下，散列表的查找（獲取給定索引處的值）速度與數組一樣快，而插入和刪除速 度與鏈表一樣快，因此它兼具兩者的優點！但在最糟情況下，散列表的各種操作的速度都很慢。 因此，在使用散列表時，避開最糟情況至關重要。為此，需要避免沖突。而要避免沖突，需要有：

• 較低的填裝因子；
• 良好的散列函數。

5.5，小結

散列表是一種功能強大的數據結構，其操作速度快，還能讓你以不同的方式建立數據模型。 你可能很快會發現自己經常在使用它。

• 你可以結合散列函數和數組來創建散列表。
• 沖突很糟糕，你應使用可以最大限度減少沖突的散列函數。
• 散列表的查找、插入和刪除速度都非常快。
• 散列表適合用于模擬映射關系。
• 一旦填裝因子超過0.7，就該調整散列表的長度。
• 散列表可用于緩存數據（例如，在Web服務器上）。
• 散列表非常適合用于防止重復。

第六章，廣度優先搜索

圖算法：廣度優先搜索（breadth-first search, BFS）算法
廣度優先搜索讓你能夠找出兩樣東西之間的最短距離，不過最短距離的含義有很多！使用廣度優先搜索可以：

• 編寫國際跳棋AI，計算最少走多少步就可獲勝；
• 編寫拼寫檢查器，計算最少編輯多少個地方就可將錯拼的單詞改成正確的單詞，如將 READED改為READER需要編輯一個地方；
• 根據你的人際關系網絡找到關系最近的醫生。

解決最短路徑問題的算法被稱為廣度有限算法，一般步驟為：

使用圖來建立問題模型。

使用廣度優先搜索解決問題。

6.1，圖是什么

圖由節點（node）和邊（edge）組成。

6.2，廣度優先搜索

在廣度優先搜索的執行過程中，搜索范圍從起點開始逐漸向外延伸，即先檢查一度關系，再檢查二度關系。

6.3，棧與隊列

• 棧：后進先出（Last In First Out，LIFO）的數據結構
• 隊列：先進先出（First In First Out，FIFO）的數據結構，支持入隊和出對操作。

6.4，代碼實現圖結構

圖中每個節點都與相鄰節點相連，散列表結構可以表示這種關系。
圖分為有向圖（directed graph）和無向圖（undirected graph），有向圖關系是單向的，無向圖沒有箭頭，直接相連的節點互為鄰居。對從自己出發有指向他人的箭頭，則有鄰居。

6.4.1 運行時間

如果你在你的整個人際關系網中搜索芒果銷售商，就意味著你將沿每條邊前行（記住，邊是從一個人到另一個人的箭頭或連接），因此運行時間至少為 $O(邊數)$。你還使用了一個隊列，其中包含要檢查的每個人。將一個人添加到隊列需要的時間是固定的，即為 $O(1)$，因此對每個人都這樣做需要的總時間為 $O(人數)$。所以，廣度優先搜索的運行時間為 $O(人數+邊數)$，這通常寫作 $O(V+E)$，其中 $V$ 為頂點（ vertice）數， $E$ 為邊數。

第七章，迪克斯特拉算法

7.1，使用迪克斯特拉算法

迪克斯特拉算法能夠找出加權圖中前往X的最短路徑。對于尋找耗時最少的路徑，迪克斯特拉算法包含４個步驟：

找出“最便宜”的節點，即可在最短時間內到達的節點。

更新該節點的鄰居的開銷，其含義將稍后介紹。

重復這個過程，直到對圖中的每個節點都這樣做了。

計算最終路徑。

每個節點都有開銷。開銷指的是從起點前往該節點需要多長時間。

7.2，術語

• 帶權重的圖稱為加權圖（ weighted graph），不帶權重的圖稱為非加權圖（ unweighted graph）。
• 要計算非加權圖中的最短路徑，可使用廣度優先搜索。要計算加權圖中的最短路徑，可使用狄克斯特拉算法。
• 在無向圖中，每條邊都是一個環。狄克斯特拉算法只適用于有向無環圖（ directed acyclic graph， DAG）。

圖可能有環，所謂環，是指由一個節點出發，走一圈后可以又回到原節點，如下圖所示：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-nvShzYxH-1664372500329)(…/data/images/7.2環示意圖.png)]

7.3，負權邊

因此， 不能將狄克斯特拉算法用于包含負權邊的圖。在包含負權邊的圖中，要找出最短路徑，可使用另一種算法——貝爾曼?福德算法（ Bellman-Ford algorithm）。

7.4，編程實現狄克斯特拉算法

以下圖為例，編程實現耗時最短的路徑。

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-IROpVHMd-1664372500334)(…/data/images/7.4圖算法問題.png)]

代碼如下：

# 為了實現帶權圖，可使用散列表，散列表用Python字典實現 graph = {} # 存儲起始節點鄰居和前往鄰居的開銷 graph['start'] = {} graph["start"]["a"] = 6 graph["start"]["b"] = 2 print(graph["start"].keys()) # 添加其他節點及其鄰居 graph["a"] = {} graph["a"]["fin"] = 1graph["b"] = {} graph["b"]["a"] = 3 graph["b"]["fin"] = 5# 終點沒有任何鄰居 graph['fin'] = {}# 創建存儲每個節點開銷的開銷表 infinity = float("inf") costs = {} costs["a"] = 6 costs["b"] = 2 costs["fin"] = infinity# 創建存儲父節點的散列表 parents = {} parents["a"] = "start" parents["b"] = "start" parents["fin"] = None # 創建一個數組，用于記錄處理過的節點 processed = []# 找出開銷最低的節點 def find_lowest_cost_node(costs):lowest_cost = float("inf")lowest_cost_node = Nonefor node in costs:cost = costs[node]if cost < lowest_cost and node not in processed:lowest_cost = costlowest_cost_node = nodereturn lowest_cost_node# 在未處理的節點中找出開銷最小的節點 node = find_lowest_cost_node(costs) while node is not None:cost = costs[node]neighbors = graph[node]# 遍歷當前節點的鄰居for n in neighbors.keys():new_cost = cost + neighbors[n]# 如果當前節點前往該鄰居更近，就更新該鄰居的開銷, 同時將該鄰居的父節點設置為當前節點if costs[n] > new_cost:costs[n] = new_costparents[n] = node# 將當前節點標記為處理過processed.append(node) # 找出接下來要處理的節點，并循環node = find_lowest_cost_node(costs)print("Cost from the start to each node:") print(costs)

7.5，小結

• 廣度優先搜索用于在非加權圖中查找最短路徑。
• 狄克斯特拉算法用于在加權圖中查找最短路徑。
• 僅當權重為正時狄克斯特拉算法才管用。
• 如果圖中包含負權邊，請使用貝爾曼?福德算法。

第八章，貪婪(貪心)算法

貪婪算法思想很簡單：每步都采取最優的做法，專業術語說，就是每步都選擇局部最優解，最終得到的就是全局最優解。

8.1，教室調度問題

根據給定課表，盡可能將更多的課程安排在某間教室。解決辦法：貪婪算法可找到最優解。

8.2，背包問題

背包重量有限，根據策略使得裝入背包的物品價值最高。
在這里， 貪婪策略顯然不能獲得最優解，但非常接近。在有些情況下，完美是優秀的敵人。有時候，你只需找到一個能夠大致解決問題的算法，此時貪婪算法正好可派上用場，因為它們實現起來很容易，得到的結果又與正確結果相當接近。

8.3，集合覆蓋問題

每個廣播臺都覆蓋特定區域的州，找出覆蓋全美50個州的最小廣播集合。
貪婪算法解決這個問題，當廣播臺數量過多，算法所耗費的時間將激增。

8.3.1，近似算法

集合覆蓋問題舉例：每個廣播臺都覆蓋特定區域的州，找出覆蓋全美50個州的最小廣播集合。貪婪算法可以解決這個問題，當廣播臺數量過多，算法所耗費的時間將激增。

選出這樣一個廣播臺，即它覆蓋了最多的未覆蓋州。即便這個廣播臺覆蓋了一些已覆蓋的州，也沒有關系。

重復第一步，直到覆蓋了所有的州。

這是一種近似算法（ approximation algorithm） 。在獲得精確解需要的時間太長時，可使用近似算法。判斷近似算法優劣的標準如下：

• 速度有多快；
• 得到的近似解與最優解的接近程度。

代碼實例：

""" 準備工作 """ # 創建一個列表，包含要覆蓋的州 states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"]) # 廣播臺清單 stations = {} stations["kone"] = set(["id", "nv", "ut"]) stations["ktwo"] = set(["wa", "id", "mt"]) stations["kthree"] = set(["or", "nv", "ca"]) stations["kfour"] = set(["nv", "ut"]) stations["kfive"] = set(["ca", "az"]) # 定義一個集合存儲最終選擇的廣播臺 final_stations = set() """ 計算答案 """ best_station = None while states_needed:best_station = Nonestates_covered = set()for station, states in stations.items():covered = states_needed & statesif len(covered) > len(states_covered):best_station = stationstates_covered = coveredstates_needed -= states_coveredfinal_stations.add(best_station) print(final_stations)

程序輸出如下：

{‘kone’, ‘ktwo’, ‘kthree’, ‘kfive’}

貪心算法的實質是每次選出當前的最優解，不管整體，是基于一定假設下的最優解。

8.4，NP完全問題

旅行商問題和集合覆蓋問題有一些共同之處：你需要計算所有的解，并從中選出最小/最短的那個。這兩個問題都屬于NP完全問題。NP完全問題的簡單定義是，以難解著稱的問題，如旅行商問題和集合覆蓋問題。很多非常聰明的人都認為，根本不可能編寫出可快速解決這些問題的算法。

8.4.1，如何識別NP完全問題

NP 完全問題無處不在！如果能夠判斷出要解決的問題屬于 NP 完全問題就好了，這樣就不用 去尋找完美的解決方案，而是使用近似算法即可。但要判斷問題是不是NP完全問題很難，易于解決的問題和 NP 完全問題的差別通常很小。

但如果要找出經由指定幾個點的的最短路徑，就是旅行商問題——NP完全問題。簡言之，沒辦法判斷問題是不是 NP 完全問題，但還是有一些蛛絲馬跡可循的。

• 元素較少時算法的運行速度非?？?#xff0c;但隨著元素數量的增加，速度會變得非常慢。
• 涉及“所有組合”的問題通常是NP完全問題。
• 不能將問題分成小問題，必須考慮各種可能的情況。這可能是NP完全問題。
• 如果問題涉及序列（如旅行商問題中的城市序列）且難以解決，它可能就是NP完全問題。
• 如果問題涉及集合（如廣播臺集合）且難以解決，它可能就是NP完全問題。
• 如果問題可轉換為集合覆蓋問題或旅行商問題，那它肯定是NP完全問題。

8.5，小結

• 貪婪算法尋找局部最優解，企圖以這種方式獲得全局最優解。
• 對于NP完全問題，還沒有找到快速解決方案。
• 面臨NP完全問題時，最佳的做法是使用近似算法。
• 貪婪算法易于實現、運行速度快，是不錯的近似算法。

第九章，動態規劃

9.1，概念

動態規劃算法是通過拆分問題，定義問題狀態和狀態之間的關系，使得問題能夠以遞推（或者說分治）的方式去解決。在學習動態規劃之前需要明確掌握幾個重要概念，如下：

• 階段：對于一個完整的問題過程，適當的切分為若干個相互聯系的子問題，每次在求解一個子問題，則對應一個階段，整個問題的求解轉化為按照階段次序去求解。
• 狀態：狀態表示每個階段開始時所處的客觀條件，即在求解子問題時的已知條件。狀態描述了研究的問題過程中的狀況。
• 決策：決策表示當求解過程處于某一階段的某一狀態時，可以根據當前條件作出不同的選擇，從而確定下一個階段的狀態，這種選擇稱為決策。
• 策略：由所有階段的決策組成的決策序列稱為全過程策略，簡稱策略。
• 最優策略：在所有的策略中，找到代價最小，性能最優的策略，此策略稱為最優策略。
• 狀態轉移方程：狀態轉移方程是確定兩個相鄰階段狀態的演變過程，描述了狀態之間是如何演變的。

9.2，背包問題

學習動態規劃，這是一種解決棘手問題的方法，它將問題分成小問題，并先著手解決這些小問題，每個動態規劃問題都是從一個網格入手，背包問題的網格如下：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-BtcVv2ps-1664372500337)(…/data/images/9.2-背包問題.jpg)]

工作原理：動態規劃先解決子問題，再逐步解決大問題。從背包問題的網格計算入手，可明白為何計算小背包可裝入的商品的最大價值。余下了空間時，你可根據這些子問題的答案來確定余下的空間可裝入哪些商品。計算每個單元格的價值時，使用的公式都相同。 這個公式如下：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-bQDVmanL-1664372500338)(…/data/images/9.2-背包問題公示圖.png)]

網格的行順序發生變化時，最終答案沒有變化。各行的排列順序對最終結果無關緊要。

動態規劃功能強大，它能夠解決子問題并使用這些答案來解決大問題。 但僅當每個子問題都是離散的，即不依賴于其他子問題時，動態規劃才管用。 這意味著使用動態規劃算 法解決不了去巴黎玩的問題。

9.1，最長公共子串

通過動態規劃問題，得到以下啟示：

• 動態規劃可幫助你在給定約束條件下找到最優解在背包問題中，你必須在背包容量給定的情況下，偷到價值最高的商品。
• 在問題可分解為彼此獨立且離散的子問題時，就可使用動態規劃來解決。
  要設計出動態規劃解決方案可能很難，這正是本節要介紹的。下面是一些通用的小貼士：
• 每種動態規劃解決方案都涉及網格。
• 單元格中的值通常就是你要優化的值。在前面的背包問題中，單元格的值為商品的價值。
• 每個單元格都是一個子問題，因此你應考慮如何將問題分成子問題，這有助于你找出網格的坐標軸。

第十章，K最近鄰算法

第十一章　接下來如何做

總結

以上是生活随笔為你收集整理的算法图解笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。