資訊專欄INFORMATION COLUMN
摘要：代碼實現見下面評論對應代碼動態規劃基本思想和分治法基本思想有共同的地方，不同的是子問題往往不是獨立的，有事母問題要借助子問題的解來判斷，因此把已經計算好的問題記錄在表格中，后續如果需要查詢一下，可以避免重復計算，這是動態規劃的基本思想。
作者：心葉
時間：2018-05-01 19:28
本文對應github地址：https://github.com/yelloxing/...
以上實現了常見算法的java、c語言、javascrpt（或node.js）、python3和go語言實現，持續更新中。
下面針對一些基本的算法思想，給出大致的說明和用例。
遞歸與分治策略 分治法的基本思想把一個規模為n的問題分解為k個規模較小的子問題，這些子問題相互獨立且與原問題相同，遞歸的解這些子問題，然后把各個子問題的解合并得到原問題的解。
算法使用例子【題目】
使用快速排序方法排列一個一維數組。
【思路】
對于輸入的子數組a[p:r]，按照一下3個步驟進行排序：
1）分解divide：以a[p]為基準元素將a[p:r]劃分成3段a[p:q-1]，a[q]和a[q+1:r]，其中a[q]不小于a[p:q-1]中的任何元素且不大于a[q+1:r]中的任何元素，下標q在劃分中確定。
2）遞歸求解conquer：通過遞歸調用排序，分別對a[p:q-1]和a[q+1:r]進行排序。
3）合并merge：合并a[p:q-1]，a[q]和a[q+1:r]返回為最終結果。
【代碼實現】
見下面評論對應代碼
動態規劃 基本思想和分治法基本思想有共同的地方，不同的是子問題往往不是獨立的，有事母問題要借助子問題的解來判斷，因此把已經計算好的問題記錄在表格中，后續如果需要查詢一下，可以避免重復計算，這是動態規劃的基本思想。
不過動態規劃具體實現起來多種多樣，不過都具有相同的填表格式，通常按照下面步驟設計算法：
1）找出最優解的性質，并刻畫其結構特征；
2）遞歸的定義最優值；
3）以自底向上的方式計算出最優值；
4）通過計算最優值時刻意記錄的判斷結果來構造最優解。
可以使用該算法思想設計算法的問題一般會具有二個決定性的性質：
1）最優子結構性質；
2）子問題重疊性質。
和上面的算法思想差不多，不同的是備忘錄為每個解過的子問題建立備忘錄以備需要的時候查看，避免了相同的問題計算多次。
一般來說，當一個問題的所有子問題都至少要解一次時，用動態規劃比備忘錄要好，因為不會有任務暫存且沒有多余的計算；當子問題空間中部分問題不必解時，用備忘錄比較好。
不過上面不是絕對的，這樣說只是想區別一下二個思想的不同，具體的時候還是要根據業務場景來在保證可行的前提下選擇更好的方法。
算法使用例子【題目】
給定n個矩形{A1,A2,...,An},其中Ai與Ai+1是可乘的，由于矩陣滿足結合律，不同的加括號方法計算次數不一樣，求最優的加括號方法。
【思路】
分別計算有1，2，3，...，n個矩陣的最優解，計算i個時候，全部的i-1的最優解已經記錄下來了，保證計算不重復。
【代碼實現】
見下面評論對應代碼
貪心算法 基本思想算法思想很簡單，和字面意思一樣，每次都選擇對自己最有利的，不過這是有條件的，只有在滿足條件下每次選擇最有利自己的才可以獲取最優解。
貪心選擇性質和最優子結構性質是該思想最重要的性質：
1）貪心選擇性質：所求問題的整體最優解可以通過一系列局部最優的選擇達到。
2）最優子結構性質：當一個問題的最優解包含其子問題的最優解時，稱此問題具有此性質。
【題目】
有一批集裝箱要裝上一艘載重為c的輪船，其中集裝箱i的重量為wi，要求在裝貨體積不受限制的條件下盡力多裝集裝箱的解。
【思路】
先排序，然后選擇從最輕的開始裝貨物。
【代碼實現】
這里就不提供具體代碼了，因為感覺沒有什么意義，最重要的是要先確定問題滿足貪心選擇性質，這樣在很多時候，可以更容易的解決問題，這點很重要。
回溯法 基本思想說的直白點就是深度優先方式系統搜索問題的算法。
算法使用例子【題目】
有一批共n個集裝箱要裝上兩艘載重方別為c1和c2的輪船上，其中集裝箱i的重量為wi，且全部集裝箱重量不大于兩艘載重之和，問是否有一個裝載方案完成裝載。
【思路】
對第一艘船，構造一個0/1樹，0代表不選擇，1代表選擇，然后分別去從根節點試圖爬到葉節點，去一一記錄下來可行的，選擇最小的為解，余下的判斷第二艘船是否裝的下即可。
【代碼實現】
見下面評論對應代碼
分支限界 基本思想對比回溯法就很容易思考，用廣度優先的辦法，不斷擴大當前節點的孩子為當前節點，主要是求解一個最優解，算法相比回溯法要簡單些。
算法使用例子【題目】
有一批共n個集裝箱要裝上兩艘載重方別為c1和c2的輪船上，其中集裝箱i的重量為wi，且全部集裝箱重量不大于兩艘載重之和，問是否有一個裝載方案完成裝載。
【思路】
借助隊列，一層層來檢查，找到最優解。
【代碼實現】
見下面評論對應代碼
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/107711.html
摘要：本文總結了前端老司機經常問題的一些問題并結合個人總結給出了比較詳盡的答案。網易阿里騰訊校招社招必備知識點。此外還有網絡線程，定時器任務線程，文件系統處理線程等等。線程核心是引擎。主線程和工作線程之間的通知機制叫做事件循環。 showImg(https://segmentfault.com/img/bVbu4aB?w=300&h=208); 本文總結了前端老司機經常問題的一些問題并結合個...
摘要：本文總結了前端老司機經常問題的一些問題并結合個人總結給出了比較詳盡的答案。網易阿里騰訊校招社招必備知識點。此外還有網絡線程，定時器任務線程，文件系統處理線程等等。線程核心是引擎。主線程和工作線程之間的通知機制叫做事件循環。 showImg(https://segmentfault.com/img/bVbu4aB?w=300&h=208); 本文總結了前端老司機經常問題的一些問題并結合個...
摘要：本文總結了前端老司機經常問題的一些問題并結合個人總結給出了比較詳盡的答案。網易阿里騰訊校招社招必備知識點。此外還有網絡線程，定時器任務線程，文件系統處理線程等等。線程核心是引擎。主線程和工作線程之間的通知機制叫做事件循環。 showImg(https://segmentfault.com/img/bVbu4aB?w=300&h=208); 本文總結了前端老司機經常問題的一些問題并結合個...
摘要：程序員小吳打算使用動畫的形式來幫助理解遞歸，然后通過遞歸的概念延伸至理解動態規劃算法思想。因此，分治策略一般用來解決子問題相互對立的問題，稱為標準分治，而動態規劃用來解決子問題重疊的問題。難點就在于找出動態規劃中的這三個概念。 在學習「數據結構和算法」的過程中，因為人習慣了平鋪直敘的思維方式，所以「遞歸」與「動態規劃」這種帶循環概念（繞來繞去）的往往是相對比較難以理解的兩個抽象知識點。...
閱讀 992·2021-11-23 09:51
閱讀 3481·2021-11-22 12:04
閱讀 2725·2021-11-11 16:55
閱讀 2950·2019-08-30 15:55
閱讀 3236·2019-08-29 14:22
閱讀 3360·2019-08-28 18:06
閱讀 1249·2019-08-26 18:36
閱讀 2136·2019-08-26 12:08
