(本文參考 OI Wiki )

一、枚舉法

枚舉的思想是不斷地猜測，從可能的集合中一一嘗試，然后再判斷題目的條件是否成立。

要點：

1）給出解空間：在一定范圍內(nèi)，可能發(fā)生的情況是什么？

2）減少枚舉的空間：目的是減少不必要的開銷

3）選擇合適的枚舉順序：根據(jù)題目要求，選擇最合理的枚舉順序

二、模擬

模擬就是用計算機來模擬題目中要求的操作。

模擬題目通常具有碼量大、操作多、思路繁復的特點。

三、遞歸

遞歸，在數(shù)學和計算機科學中是指在函數(shù)的定義中使用函數(shù)自身的方法，在計算機科學中還額外指一種通過重復將問題分解為同類的子問題而解決問題的方法。

什么是遞歸？

遞歸的基本思想是某個函數(shù)直接或者間接地調(diào)用自身，這樣原問題的求解就轉(zhuǎn)換為了許多性質(zhì)相同但是規(guī)模更小的子問題。求解時只需要關(guān)注如何把原問題劃分成符合條件的子問題，而不需要過分關(guān)注這個子問題是如何被解決的。

遞歸的例子：

如何給一堆數(shù)字排序？答：分成兩半，先排左半邊再排右半邊，最后合并就行了，至于怎么排左邊和右邊，請重新閱讀這句話。

遞歸代碼最重要的兩個特征：結(jié)束條件和自我調(diào)用。自我調(diào)用是在解決子問題，而結(jié)束條件定義了最簡子問題的答案。

int func(傳入數(shù)值){

if(終止條件)? return最小子問題解;? //結(jié)束條件

return func(縮小規(guī)模);? //自我調(diào)用

}

為什么要寫遞歸？

1、遞歸結(jié)構(gòu)清晰，可讀性強。

2、使用遞歸能練習分析問題的結(jié)構(gòu)。當發(fā)現(xiàn)問題可以被分解成相同結(jié)構(gòu)的小問題時，遞歸寫多了就能敏銳發(fā)現(xiàn)這個特點，進而高效解決問題。

遞歸的缺點：

1）在程序執(zhí)行中，遞歸是利用堆棧來實現(xiàn)的。每當進入一個函數(shù)調(diào)用，棧就會增加一層棧幀，每次函數(shù)返回，棧就會減少一層棧幀。而棧不是無限大的，當遞歸層數(shù)過多時，就會造成?棧溢出?的后果。

2）顯然有時候遞歸處理是高效的，比如歸并排序；有時候是低效的，因為堆棧會消耗額外空間，而簡單的遞推不會消耗空間。

遞歸優(yōu)化：

主頁面：搜索優(yōu)化 和 記憶化搜索

比較初級的遞歸實現(xiàn)可能遞歸次數(shù)太多，容易超時。這時需要對遞歸進行優(yōu)化。

寫遞歸的要點：

明白一個函數(shù)的作用并相信它能完成這個任務，千萬不要跳進這個函數(shù)里面企圖探究更多細節(jié)

四、分治

分治算法的核心思想就是“分而治之”。

大概的流程可以分為三步：分解 -> 解決 -> 合并。

1、分解原問題為結(jié)構(gòu)相同的子問題。

2、分解到某個容易求解的邊界之后，進行遞歸求解。

3、將子問題的解合并成原問題的解。

分治法能解決的問題一般有如下特征：

1）問題規(guī)模較小：該問題的規(guī)模縮小到一定的程度就可以容易地解決。

2）問題可以分解與合并：該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，利用該問題分解出的子問題的解可以合并為該問題的解。

3）分解的子問題是獨立的：該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。

注意：（如果各子問題是不獨立的，則分治法要重復地解公共的子問題，也就做了許多不必要的工作。此時雖然也可用分治法，但一般用 動態(tài)規(guī)劃??較好。）

區(qū)別：

遞歸與枚舉：

遞歸和枚舉的區(qū)別在于：枚舉是橫向?地把問題劃分，然后依次求解子問題；而遞歸是把問題逐級分解，是縱向?的拆分。

遞歸與分治：

遞歸是一種編程技巧，一種解決問題的思維方式?；分治算法很大程度上是基于遞歸的，解決更具體問題的算法思想。