下面用LeetCode上的一個(gè)爬樓梯問題給出遞歸和分治兩種解法來對(duì)比典予。
假設(shè)你正在爬樓梯，需要n階才能到達(dá)樓頂（n是一個(gè)正整數(shù)）乐严，每次你可以爬1或2個(gè)臺(tái)階熙参，有多少種不同的方法可以爬到樓頂？
這個(gè)問題每走3階就要重新選擇爬1階或者兩階麦备，很明顯我們可以把一個(gè)大問題拆解成一個(gè)一個(gè)的小問題孽椰，可以使用遞歸來解決。
遞歸方程式：f(n) = f(n-1)+f(n-2)
遞歸的結(jié)束條件是我們已知的：f(1) = 1; f(2) = 2;
代碼如下：
int upStairs1(int n) {
if (n < 1) return 0;
if (n == 1) return 1;
if (n == 2) return 2;
return upStairs1(n-1)+upStairs1(n-2);
}
使用動(dòng)態(tài)規(guī)劃法凛篙，開辟n+1個(gè)內(nèi)存空間來存儲(chǔ)每一步的值：
int upStairs2(int n) {
if (n == 1) return 1;
int *times = (int *)malloc(sizeof(int)*(n+1));
times[0] = 0;
times[1] = 1;
times[2] = 2;
for (int i = 3; i < n+1; i++) {
times[i] = times[i-1]+times[i-2];
}
return times[n];
}
兩種算法的時(shí)間復(fù)雜度：遞歸的時(shí)間復(fù)雜度是n的平方黍匾，分治法復(fù)雜度為n。從空間角度來看呛梆，使用遞歸锐涯，多個(gè)函數(shù)嵌套調(diào)用，系統(tǒng)會(huì)開辟一個(gè)“遞歸工作椞钗铮”作為整個(gè)函數(shù)運(yùn)行期間的數(shù)據(jù)存儲(chǔ)纹腌，空間上的耗費(fèi)是很大的，而分治法則只需要開辟一段存儲(chǔ)空間來存儲(chǔ)整形數(shù)據(jù)滞磺。綜合來看升薯，我們還是要盡量避免遞歸的使用。動(dòng)態(tài)規(guī)劃法是個(gè)很好的選擇击困。
