在介紹此算法之前，我線拋出幾道題目，當(dāng)然這幾道題目均出自于劍指offer大家可以簡(jiǎn)單思考一下。
Q1:大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù)n，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)。
Q2:一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。
Q3:一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。
Q4:我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問(wèn)用n個(gè)21的小矩形無(wú)重疊地覆蓋一個(gè)2*n的大矩形，總共有多少種方法？
第一道題我想大學(xué)剛學(xué)C的時(shí)候上機(jī)實(shí)驗(yàn)就應(yīng)該有這道題，一道很簡(jiǎn)單的遞歸題，代碼如下。
public class Solution {
public int Fibonacci(int n) {
if(n>39){
return -1;
}
if(n == 0){
return 0;
}
if(n == 1){
return 1;
}
return Fibonacci(n-1)+Fibonacci(n-2);
}
}
然而第二，三，四題呢?有沒(méi)有具體的解題思路呢?所以，我認(rèn)為，在解決這種一眼看上去很簡(jiǎn)單，但是又無(wú)從下手給出具體的代碼思路的時(shí)候，通?？梢杂脭?shù)學(xué)歸納法
首先我們來(lái)看第一題：
我們?cè)O(shè)臺(tái)階一共有n級(jí)，當(dāng)n=1，2，3，4時(shí)分別有幾種跳法呢？
n=1；jumpWays=1(即：1);
n=2；jumpWays=2(即：1-1,2);
n=3；jumpWays=3(即：1-1-1,1-2,2-1);
n=4；jumpWays=5(即：1-1-1-1,1-2-1,2-1-1,1-1-2,2-2);
好了，接下來(lái)就不用繼續(xù)往下推了吧？而且大家很容易就能歸納出來(lái)即：
f(n) = f(n-2)+f(n-1),當(dāng)n==1時(shí)，return1；當(dāng)n==2時(shí)，return 2；
這不就是斐波那契數(shù)列嗎？
代碼如下
public class Solution {
public int JumpFloor(int target) {
if(target == 1){
return 1;
}
if(target == 2){
return 2;
}
return JumpFloor(target-1)+JumpFloor(target-2);
}
}
同樣我們來(lái)看第二題：
我們?cè)O(shè)臺(tái)階一共有n級(jí)，當(dāng)n=1，2，3，4時(shí)分別有幾種跳法呢？
n=1；jumpWays=1(即：1);
n=2；jumpWays=2(即：1-1,2);
n=3；jumpWays=4(即：1-1-1,1-2,2-1,3);
n=4；jumpWays=8(即：1-1-1-1,1-2-1,2-1-1,1-1-2,2-2,1-3,3-1,4);
好了，接下來(lái)就不用繼續(xù)往下推了吧？而且大家很容易就能歸納出來(lái)即：
f(n) = 2的n-1次方，當(dāng)n==1時(shí)，return 1；（這里貌似簡(jiǎn)書(shū)markdown不支持函數(shù)格式？ex:2^{n-1}）
代碼如下
public class Solution {
public int JumpFloorII(int target) {
if(target == 1){
return 1;
}
return 2*JumpFloorII(target-1);
}
}
最后一題當(dāng)然留給大家自己思考?xì)w納一下了？我認(rèn)為這樣才能有收獲的??。
最后總結(jié)一下：我認(rèn)為呢？通常碰到那種看上去邏輯簡(jiǎn)單的，但是沒(méi)有思路去寫(xiě)代碼的時(shí)候，不妨利用數(shù)學(xué)歸納法，推理一下當(dāng)n很小的時(shí)候的幾種情況，看看能不能從中找出規(guī)律。
