1樓：冒泡
因為題主說的這幾個詞，都是一種思想而非演算法，具體的演算法是思想的糅合
先區分bfs和dfs，這個應該比較明確
dfs的時候，如果發現走不通，返回去選擇另外的決策分支搜尋，這個就是回溯思想
如果你的搜尋模型是一棵樹，dfs過程中發現兩個子樹的計算過程等價，就只計算一次並儲存結果，這個是記憶化搜尋，dp思想的一種體現
或者，你bfs這棵樹，對相同狀態的節點的結果做合併處理，也是dp思想，這個做法還可以擴充套件到圖中，具體到求最短路徑之類的問題上，合併結果的處理一般也叫做「鬆弛」
dfs可以用遞迴來實現
分治則是大問題分成小問題，一般來說配合dfs用
另外，如果你bfs或dfs過程中，因為某種理由，發現某個節點沒必要繼續下去了，這是剪枝
如果你每次決策的多個分支，可以證明你選最好的乙個就行，就成了貪心了
個人的理解，都是搜尋思路的優化
附：如何理解動態規劃？
2樓：Mike
當你程式設計編的多了，你就會發現
dynammic programming 是 incursive 的另一種叫法。
而遞迴就是 recursive。
前者是從下面直接往上磊；後者是從上面往下找，然後再磊回去。因此，在模型相同的情況下，recursive 是比 incursive 要更加緩慢。
3樓：王曉遠
想對於與其他答主, 我倒認為這是乙個很好的問題.
而且樓主的感覺是正確的.
這些都是同一種計算機思想的不同體現:自上而下思考,分解並合併子問題
理解了這個思想, 具體叫什麼其實關係不大了.
計算機擅長的是解決同乙個問題 (一般定義成乙個函式),
只是解空間的大小(引數)不同而已
通過組合不同子問題的解, 以獲得當前的解
而關鍵在於子問題的拆法, 或者說狀態的定義和狀態間的轉移.
比如歸併排序, 將解空間拆成原來的1/2(分治), 當兩個子問題解決之後, 再簡單合起來即使當前解
快速排序, 通過隨機pivot將整個陣列隔離成兩個不相交的陣列, 分別再解決兩個子問題即可
包括斐波那契數列, 漢諾塔問題無不是如此
複雜一點的如動態規劃, 也是自上而下思考, 定義子問題, 通過解決子問題, 然後再根據多個子問題推導出當前問題的最優值.
像編輯距離Edit Distance, LCS, 數字三角形等
這個過程可以用遞迴實現, 為了不重複計算會用陣列或map來記錄每個解空間的最優解(叫備忘錄?)
但往往為了避免棧溢位, 需要自底向上實現. 類似dp[x][y]這樣
又比如貪心, Leetcode 3. Longest Substring Without Repeating Characters, 定義每個位置的往前的非重複字串長度為f(i). 那麼f(i)只取決於f(i-1)和當前字元的上乙個出現位置.
所以當前最優解只依賴於乙個子問題. 從這個意義上講, 貪心是動態規劃的乙個特例.
而BFS, DFS是兩種基本搜尋演算法, 從廣度或者深度出發, 這個應該很好理解.
所以BFS使用佇列, DFS使用棧, 只是順序選擇的不同造成搜尋順序不同而已.
而實際中很多演算法會涉及的搜尋, 會選擇一種來使用.
總結一下,
遞迴 / DP / 貪心 / 回溯 / 分治本質上是一回事情, 只是實現方式不一樣而已
做演算法時候, 深入理解遞迴思想, 自上而下思考. 很多零散的感念就能串起來了.
還有學習演算法和具體語言關係不大.
Good Luck!
自編一道動規題，可以從哪幾個方面增加難度
把DP域拽到日期上，要求他們判閏年，狠一點的可以要求把1582年10月5日 1582年10月14日那消失的10天也考慮進去。輸入輸出要求使用羅馬數字，或者輸入上套一層表示式求值。要求輸出方案，還要求方案的字典序最小。把題面描述寫得含糊其辭可以有多種理解，把樣例出得怎麼理解都是對的。最後偷偷配上一組錯...