最近一直在學習Deep Frist Search，也在leetcode上練習了不少題目。從最開始的懵懂，到現在遇到問題基本有了思路。依然清晰的記得今年2月份剛開始刷題的時做subsets的那個吃力勁，腦子就是轉不過來到底該如何的遞歸，甚至試過使用debugger一步步的來看看堆棧到底是如何調用和返回的。經過了幾個月的訓練后，答題有了一些心得，記錄下來，作為總結。

　　遞歸函數的整體結構：

　　返回值。進入入遞歸函數的第一件事就是寫出遞歸終止的條件。通常遞歸終止的條件分為兩類：

　　（1）有一個深度的標準，例如N-Queen問題，當我們遞歸的檢測完第N個皇后，就到達來遞歸返回的條件，此時，將此次遞歸的結果作為一個解決方案存儲。

　　（2）到達一個序列（數組／字符串）vector／string.size()的位置，例如subsets，permutation和word break ii的問題，當傳遞的參數已經無法索引數組／字符串的值時退出遞歸。

　　是否進行prune的操作。這個操作并不是一定會存在的。當需要prune的時候，通常是遇到了效率問題。當輸入問題的規模非常大，存儲之前已經做過檢測或者得出結果的遞歸位置會大大降低遞歸的工作量。這個時候我們通常會利用一些數據結構。最簡單的就是一個數組，復雜一點的會是一個hash table（word break ii in leetcode）。

　　本層的遞歸處理以及下一層次的遞歸調用。這一部分是遞歸的核心，如果這一部分模型處理正確，遞歸的調用就成功了90%（很像如果能寫出動態規劃的狀態方程的感覺）。

　　返回值。最后的return，連同遞歸的處理和調用，具體內容會這下面詳細闡述。

　　遞歸函數的類型：

　　總的來說DFS的函數分為兩種類型，有返回值和沒有返回值。遞歸的層次都是通過一個參數傳遞到函數內部，這兩種函數的編寫有區別，雖然都是DFS，但思維方式卻是不一樣。

　　對于無返回值的DFS函數，通常我們是將需要獲取的值作為引用類型的參數傳遞到函數內部，當到達DFS函數終止的條件時我們獲取想要得到的值，例如N-Queen，subsets， permutations等經典的問題。這是一種從上向下的思維模式。這種函數適用于求所有可能的解的問題。通常是先對該層的問題進行處理，然后再進入下一個層次的遞歸。當到達遞歸終止的條件時存儲結果。然后再逐層的返回，通常會恢復該層這遍歷之前的狀態，為的是下一個遞歸。

以下為這種遞歸的模板：

void DFS_no_return(vector<TYPE>& solution_set, TYPE& solution, int idx){// DFS terminate condition// Normally there are two major categories// One is for some number, already reach this depth according to the question, stop// get to the end of an array, stopif(idx == n || idx == (vector/string).size()){solution_set.push_back(solution);return;}// very seldom only when our program met some efficiency problem// do prune to reduce the workload// no need do DFS if we already get the value of current element, just returnif(hash_table[input] != hash_table.end()){return;}for(int i = 0; i < n; i++){if(visited[i] == 0){// do something for current level processvisited[i] = 1;// for next level DFSDFS_no_return(solution_set, solution, idx + 1);// return from lower level DFS and restore the status for next DFSvisited[i] = 0;}}return;
}

對于有返回值的DFS來說，我們需要獲得的值是遞歸函數的返回值。與無返回值的遞歸函數相比，最大的一個區別是該類遞歸函數在遞歸調用返回之后處理該層的遞歸值。將從低層次遞歸返回的值結合本層的值處理，然后再返回給上一層遞歸函數調用。這種問題的思路是由上到下，再由下向上。通常是將一個復雜的問題逐層的分解成小問題，等到無法再分則返回，再將小問題拼裝，然后逐層向上，返回大問題作為問題的解。通常在使用分治的思想時會使用有返回值的深度遞歸函數，這個應用在樹中非常普遍。

以下為有返回值的遞歸函數的模板：

TYPE DFS_with_return(int idx){// DFS terminate condition// Normally there are two major categories// One is for some number, already reach this depth according to the question, stop// get to the end of an array, stopif(idx == n || idx == (vector/string).size()){return 1/0/"";}// very seldom only when our program met some efficiency problem// do prune to reduce the workload// no need do DFS if we already get the value of current element, just returnif(hash_table[input] != hash_table.end()){return hash_table[input];}TYPE ans;for(int i = 0; i < n; i++){if(visited[i] == 0){// normally, here should to add/concatenate the value in current level with the value returned from lower levelans += DFS_no_return(idx + 1);}}// if we need prune// keep current value herehash_table[input] = ans;return ans;
}

總結：?

1. 遞歸函數的整體構造：
2. 遞歸函數的分類：
   • 無返回值：適用于求所有可能的解。
     • 是一種由上而下，將大問題分解，在每一層提取出需要處理的小問題，然后向下遞歸，遇到遞歸終止的條件時，就得到一個問題的解，此時返回。
   • 有返回值：使用與求個數／數量的問題。
     • 是一種從上向下，將大問題分解到無法再分，然后再將分解后的小問題返回，逐層進行加工處理，然后再返回給上一層調用。

轉載于:https://www.cnblogs.com/wdw828/p/6840317.html

總結

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

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