1. 模擬法簡(jiǎn)介

        在前面的文章已經(jīng)提到過(guò)模擬這個(gè)思維，模擬的思維無(wú)處不在，就樹形的DFS算法而言，我們更多的情況并非建立一棵樹，這對(duì)我們書寫和易用性而言太差了，我們通常會(huì)適用多個(gè)數(shù)組進(jìn)行模擬，樹也是可以利用數(shù)組進(jìn)行模擬的。

        如下圖：

        上面一排表示數(shù)組下標(biāo)，下面一排表示數(shù)據(jù)，其實(shí)通過(guò)這樣的簡(jiǎn)單方式，也能夠設(shè)計(jì)出一個(gè)模擬的二叉樹，其具體的表示為：

        仔細(xì)對(duì)比以下數(shù)據(jù)，可以發(fā)現(xiàn)數(shù)組中的數(shù)據(jù)存儲(chǔ)的就是與之相聯(lián)系的數(shù)組下標(biāo)，通過(guò)這樣的方式可以方便的建立一顆簡(jiǎn)單的模擬法的樹，同時(shí)再創(chuàng)建一個(gè)數(shù)組用來(lái)存儲(chǔ)具體的值，兩個(gè)數(shù)組保持一一對(duì)應(yīng)的關(guān)系就可以簡(jiǎn)單完成，這就是通過(guò)模擬算法來(lái)模擬樹結(jié)構(gòu)的核心思路，這個(gè)思路進(jìn)行擴(kuò)展其實(shí)會(huì)發(fā)現(xiàn)與建立樹，甚至是后文才會(huì)學(xué)的圖并沒(méi)有什么核心的區(qū)別。

2. 例題—全排列

        從n個(gè)不同元素中任取m（m≤n）個(gè)元素，按照一定的順序排列起來(lái)，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列。當(dāng)m=n時(shí)所有的排列情況叫全排列。

        對(duì)于常規(guī)的思路而言，我們需要對(duì)0~9一共十個(gè)數(shù)字進(jìn)行全排列，就需要列出10層for循環(huán)，每一層分別表示不同的數(shù)字，同時(shí)還需要利用if語(yǔ)句進(jìn)行判重，因此寫出來(lái)的代碼就顯得非常的累贅，其格式大致如下：

for()
    for()
        for()
            …………    省略N層for循環(huán)
                for()
                      if()

        不要小看這樣的代碼，對(duì)于一個(gè)新手而言，能夠有這樣大膽的思維，其實(shí)是很難得的，不過(guò)就后面而言，這樣的思維顯得莫過(guò)于臃腫了，而且極其不相似一種成熟的代碼，實(shí)際上，利用DFS算法，我們將10個(gè)數(shù)通過(guò)數(shù)組進(jìn)行拆分，需要多少就調(diào)用多少，同時(shí)再建立一個(gè)判斷的數(shù)組，這樣也不需要我們寫出累贅的if語(yǔ)句了，利用函數(shù)的遞歸實(shí)現(xiàn)多層的for功能。

        本例題的代碼為：

#include<iostream>
#include<cmath>
using namespace std;
 
int p[10]= {0};
bool vis[10]= {0};
int n;
void dfs(int x) {
    if (x==n+1) {
        for(int i=1; i<=n; i++)
            cout<<p[i]<<" ";
        cout<<endl;
        return ;
    }
 
    for (int i=1; i<=n; i++) {
        if (vis[i]==false  ) {
            p[x] = i;
            vis[i] = true;
            dfs(x+1);
            vis[i] = false;
        }
    }
}
 
int main() {
    while (cin>>n) {
        dfs(1);
    }
    return 0;
}

PS:這樣的全排列C++的STL庫(kù)已經(jīng)封裝好了，稱之為next_permuitation(n,n+a);

3. 例題—程序員爬樓梯

爬樓梯問(wèn)題

        爬樓梯的問(wèn)題更像我們常規(guī)的算法問(wèn)題，以是否能夠走到第4格樓梯為例，我們初始的狀態(tài)是走0個(gè)樓梯，建立二叉樹，根結(jié)點(diǎn)設(shè)置為0，隨后對(duì)于0這個(gè)狀態(tài)而言，有兩種形態(tài)，走一步和走三步，這分別對(duì)應(yīng)二叉樹的左孩子和右孩子，在走完之后，我們成功的引出了兩種狀態(tài)，共走1步和共走3步 ，我們?cè)俜謩e在這個(gè)基礎(chǔ)上重新建立左孩子和右孩子引出兩個(gè)狀態(tài)，便可以逐漸構(gòu)建出這顆二叉樹，最終，通過(guò)數(shù)最終的狀態(tài)我們可以知道一共有3個(gè)答案滿足條件。

套用DFS的模板可以輕易求解，本例題代碼為：

#include<iostream>
 
using namespace std;
 
typedef long long ll;
ll ans,n;
 
void dfs(ll k) {
    if(k==n) {
        ans++;
        return;
    } else if(k>n) {
        return;
    }
    dfs(k+1);
    dfs(k+3);
}
 
int main() {
    while(cin>>n) {
        ans=0;
        dfs(0);
        cout<<ans<<endl;
    }
    return 0;
}