核心考點：場景轉化模型，模型提取解法，簡單dp，fib
一只青蛙一次可以跳上1級臺階，也可以跳上2級，求青蛙跳上一個n級的臺階共有多少種跳法（先后次序不同算不同的結果），
決議：
對于這道題目，我們若是使用正向思維去思考，那這道題會變得非常困難，這時我們可以考慮使用逆向思維，
既然青蛙最侄訓到達第n級臺階，那青蛙必定是從第n-1級臺階或是第n-2級臺階跳到第n級臺階的，
也就是說青蛙跳到第n級臺階的總跳法數，等于青蛙跳到第n-1級臺階的總跳法數和青蛙跳到第n-2級臺階的總跳法數之和，即
f
(
n
)
=
f
(
n
?
1
)
+
f
(
n
?
2
)
f(n)=f(n-1)+f(n-2)
f(n)=f(n?1)+f(n?2)，
當然，我們不能讓這個公式一直往前推，總得給它一個盡頭，我們很容易得到青蛙跳到第0級臺階的總跳法數，和青蛙跳到第1級臺階的總跳法數：
- f ( 0 ) = 1 f(0)=1 f(0)=1，青蛙跳到第0級臺階的跳法只有一種，那就是不跳，
- f ( 1 ) = 1 f(1)=1 f(1)=1，青蛙跳到第1級臺階的跳法也只有一種，那就是從第0級臺階直接跳到第1級臺階，
這時代碼也就出來了，我們可以使用遞回來解決該問題：
//遞回
class Solution {
public:
int jumpFloor(int number) {
if (number == 0 || number == 1) //f(0)=1, f(1)=1
return 1;
return jumpFloor(number - 1) + jumpFloor(number - 2); //f(n)=f(n-1)+f(n-2)
}
};
再仔細看看這段代碼，這其實就是求第n個斐波那契數的代碼，只不過數的下標變成了從0開始而已，
因此，青蛙跳臺階的解法和求第n個斐波那契數的解法相同，使用遞回會產生大量重復計算，最優解法還是使用動態規劃，
//動規
class Solution {
public:
int jumpFloor(int number) {
if (number == 0 || number == 1) //f(0)=1, f(1)=1
return 1;
int first = 1; //f(0)=1
int second = 1; //f(1)=1
int third = 0;
while (number > 1) //進行number-1次計算
{
//f(n)=f(n-1)+f(n-2)
third = first + second;
first = second;
second = third;
number--;
}
return third;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/306287.html
標籤：其他