題目描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
我的想法
因?yàn)楹挽巢瞧踝兎N的跳臺階很像，首先想到的還是寫遞歸公式棱诱，看能不能推出什么。表面上有種f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n - (n-1))的感覺涝动，發(fā)現(xiàn)如果真的是這樣迈勋，完全可以化簡成f(n) = 2^(n-2) * f(1)，但是這當(dāng)然是錯的醋粟，細(xì)細(xì)一想就會發(fā)現(xiàn)會多出很多重復(fù)情況靡菇，這個式子完全不可取重归。
于是換一種思路，可以去選擇臺階厦凤，選擇跳上n階所踩過的臺階鼻吮。于是得出這樣的式子，f(n) = 1 + C(1, n-1) + C(2, n-2) + ... + C(n-1, n-1)较鼓，這很數(shù)學(xué)椎木。列出階乘公式，帶入很容易就ac了博烂。
代碼如下：
public class Solution {
public int JumpFloorII(int target) {
int rtn = 1;
long njie = jiecheng(target - 1);
for (int i = 1; i < target; i++) {
rtn += njie / (jiecheng(i) * jiecheng(target - 1 - i));
}
return rtn;
}
public long jiecheng(int start) {
long rtn = 1;
for (int i = start; i >= 1; i--) {
rtn *= i;
}
return rtn;
}
}
別人的思路
看到解析第一個香椎，又驚了，只有幾行代碼......思路和我的很不一樣禽篱，具體是這樣的：
f(1) = f(1-1) = 1
f(2) = f(2-1) + f(2-2) = f(1) + f(0)
f(3) = f(3-1) + f(3-2) + f(3-3) = f(2) + f(1) + f(0)
f(n) = f(n-1) + f(n-2) + ... + f(n-n) = f(0) + f(1) + f(2) + ... + f(n-1)
解釋一下就是當(dāng)跳的臺階只有一階時畜伐，只有一種跳法。
當(dāng)跳兩階臺階時躺率，可以分兩種方式烤礁，直接跳上去，另一種是先跳一階肥照，再跳上去，只是第二種方法跳過第一步后就變成跳一階的情況勤众。
了舆绎。
同樣跳三階樓梯，分三種们颜，1.先跳一階后轉(zhuǎn)換成f(2)吕朵，2.先跳兩階轉(zhuǎn)換成f(1)，3.直接跳上去窥突。
這種思路就推出了上面的公式努溃。化簡一下：
f(n-1) = f(0) + f(1) + f(2) + ... + f(n-2)
f(n) = (f(0) + f(1) + f(2) + ... + f(n-2)) + f(n-1) = 2*f(n-1)
推出來的公式真的超簡單啊阻问，代碼就沒有什么難度了
f(n) = 2*f(n-1)梧税。
public class Solution {
public int JumpFloorII(int target) {
if (target <= 1) {
return 1;
} else {
return 2 * JumpFloorII(target - 1);
}
}
}
但是畢竟這是遞歸，來看幾個優(yōu)化：
迭代：
class Solution {
public int JumpFloorII(int target) {
int rtn = 1;
while (--target != 0) {
rtn *= 2;
}
return rtn;
}
}
位運(yùn)算一行代碼：
class Solution {
public int JumpFloorII(int target) {
return 1<<(target-1);
}
}
可怕可怕称近，移位代替了乘2的工作第队，運(yùn)算速度更快。
感覺自己想到方法已經(jīng)很不容易了刨秆，看到別人的算法凳谦，感覺思維好有差距，還是要多練多練衡未。
