普通跳台階
題目：一隻青蛙一次可以跳上1級台階，也可以跳上2級台階。求該青蛙跳上一個n級的台階總共有多少種跳法？
思路：
如果台階級數大于2，設為n的話，這時我們把n級台階時的跳法看成n的函數，記為
,第一次跳的時候有2種不同的選擇：一是第一次跳一級，此時跳法的數目等于後面剩下的n-1級台階的跳法數目，即為
,二是第一次跳二級，此時跳法的數目等于後面剩下的n-2級台階的跳法數目，即為
,是以n級台階的不同跳法的總數為
，不難看出就是斐波那契數列，解法參考上一篇部落格https://blog.csdn.net/qq_40806289/article/details/89603600
變态跳台階 （這個就比較有意思了，嘿嘿）
題目描述
一隻青蛙一次可以跳上1級台階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的台階總共有多少種跳法。
思路1
假設有n個台階，可以跳萬n個台階的情況：第一次跳1個，剩餘f(n-1)種跳法，第一次跳2個，剩餘f(n-2)中跳法，。。。，先跳n個，則剩餘f(n-n)。
可以得到：f(n)=f(n-1)+f(n-2)+...+f(1)+f(0)，(n>3)(其中f(0)=1,f(1)=1,f(2)=2)。
遞歸的方法
class Solution {
public:
int jumpFloorII(int number) {
if(number==0) return 1;
if(number==1) return 1;
if(number==2) return 2;
int steps=0;
for(int i=0; i<number; i++)
{
steps += jumpFloorII(i);
}
return steps;
}
};
思路2
由思路1可知，f(n-1)=f(n-2)+f(n-3)+...+f(1)+f(0),将f(n-1)代入f(n),可得f(n)=2*f(n-1)。
class Solution {
public:
int jumpFloorII(int number) {
if(number==0) return 1;
if(number==1) return 1;
if(number==2) return 2;
int steps=2;
for(int i=3; i<=number; i++)
{
steps = 2*steps;
}
return steps;
}
};
思路3 ：
由思路2可知，f(n)=2f(n-1),且f(1)=1,f(2)=2。則f(n)=2^(n-1)。
class Solution {
public:
int jumpFloorII(int number) {
int n=1;
n<<=number-1;
return n;
}
};
矩陣覆寫
題目描述
我們可以用2*1的小矩形橫着或者豎着去覆寫更大的矩形。請問用n個2*1的小矩形無重疊地覆寫一個2*n的大矩形，總共有多少種方法？
思路：和上面的思路異曲同工，對于2*n(n>=3)的大矩形，如果使用1個小矩形豎着放在最邊上，則就成了2*（n-1）的問題了，而橫着并排放兩個則成了2*（n-2）問題。故仍舊是一個斐波那契數列（最普通的那種）。代碼同斐波那契數列的代碼。