1. DFS簡(jiǎn)介

        深度優(yōu)先搜索算法（英語：Depth-First-Search，簡(jiǎn)稱DFS）是一種用于遍歷或搜索樹或圖的算法。 沿著樹的深度遍歷樹的節(jié)點(diǎn)，盡可能深的搜索樹的分支。當(dāng)節(jié)點(diǎn)v的所在邊都己被探尋過或者在搜尋時(shí)結(jié)點(diǎn)不滿足條件，搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn)v的那條邊的起始節(jié)點(diǎn)。整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被訪問為止。屬于盲目搜索,最糟糕的情況算法時(shí)間復(fù)雜度為O(!n)，DFS搜索的過程訪問可以稱之為DFS序。

如圖：

        對(duì)于一顆這樣的樹，我們的DFS序可以為：abdefc（即時(shí)對(duì)于同一顆的樹，其DFS序不一定唯一），即訪問a之后訪問a的子結(jié)點(diǎn)b，再在b的基礎(chǔ)上依次訪問它的子結(jié)點(diǎn)def，最后回退到a處訪問c。

        這與前文花大篇幅介紹的先序，中序，后續(xù)遍歷如出一轍，唯一的不同就是這樣的一棵樹并不只存在有左右兩個(gè)結(jié)點(diǎn)，它可以是多枝的。

        而即時(shí)對(duì)于一顆深度為n的二樹，在沒有任何優(yōu)化的情況下適用DFS去搜索訪問數(shù)據(jù)，其算法的時(shí)間復(fù)雜度也高達(dá)O（2^n），在數(shù)據(jù)較大的情況下DFS是無法滿足程序的時(shí)間要求，這就會(huì)涉及到一個(gè)思路——剪枝，即通過現(xiàn)有的數(shù)據(jù)判斷接下來的數(shù)據(jù)無法再滿足解，直接將當(dāng)前結(jié)點(diǎn)以后的所有數(shù)據(jù)舍棄，遍歷不再訪問，通過精心設(shè)計(jì)的剪紙可以使得DFS搜索的效果得到很大提升。

2. 模板：

對(duì)于一個(gè)標(biāo)準(zhǔn)的DFS模板而言，其包括了以下的內(nèi)容：

bool check(參數(shù))
{
    if(滿足條件)
        return true ;
    return false;
}
 
void dfs(int step)
{
        判斷邊界
        {
            相應(yīng)操作
        }
        嘗試每一種可能
        {
               滿足check條件
               標(biāo)記
               繼續(xù)下一步dfs(step+1)
               恢復(fù)初始狀態(tài)（回溯的時(shí)候要用到）
        }
}

3. 相關(guān)配套習(xí)題

三角形（注，其還涉及了一點(diǎn)動(dòng)態(tài)規(guī)劃的思維）：

程序員爬樓梯

數(shù)的劃分