題目描述

一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。

?

相比普通青蛙跳，這個 n級的就有點難了，重點是 能跳n級，? 也就是說，只有當臺階數是1的時候，是1種跳法。

別說2階是兩種。。。

3階 還 4種， 4 階還 8種。 。。?。明顯抬杠。。。。。。。窮舉法做的吧？

因此只有將臺階 無限的化少，化少，直至 1階，這樣才能找到問題的解決辦法。

?

那就要倒著想，如果多了一階臺階，方法是多了多少呢？

因為我只知道 如果多 了一階，別 之前的 跳法多了多少，不就能求出了當前臺階的跳法了嗎。

?

數學思路：

當前臺階數的跳法，其實是 臺階數的所有 子集 臺階數的跳法(每個子集臺階，然后在直接一下跳到最后一階)。

例如 5階跳法，其實就是1階的所有跳法+2階的所有跳法+3階的所有跳法+4階的所有跳法+1（直接跳5階）。?

累加的話就需要寫一個 ?循環，將 n階 一下一下減，直到1 ，然后將所有臺階跳法 求和，實現起來也不是很難，再寫一個靜態 sum 就好， 記錄 總和

不過這樣就會 循環 調用遞歸， 遞歸本身，再次循環，勢必數據一多，就是 掛掉。

?

其他想法：

展現我靈魂畫手的實力：

假設當前有 n（示意為4） 階，跳法有x種。??

然后 加了 一階 變為 n+1?

當臺階是加在4層上面的時候：

青蛙使用? 了 x種方法? 每種方法都能跳到? n階上， 然后使用跳1 下的方法，跳上n+1階。?

?

當臺階是加在1層下面，也就是讓青蛙下一個臺階，總臺階還是 n+1 往上跳。 那么 開始跳1 ，然后剩余的 n階 還是 x種跳法。

至于臺階加在其他處，不過是將n階? “擠” 成了第5階，實質還是加了最后1階。

一次 n階方法的跳法 就是 2*(n-1) 階的跳法。

?

?

代碼：

public static int JumpFloorII(int target) {if(target==0){return 0;}if(target==1){return 1;}return JumpFloorII(--target)*2;}

?

錯誤的想法：

在我想如何組織語言，讓你們接受? 臺階加在 最頂層，還是最下層的時候，我差生了一個錯誤的想法，?

既然是 第一步跳1， 那么 我其實可以將 這多的1步，放在任何位置啊。

其實這是錯誤的想法， 這里面有嚴重的跳法重疊 。

比如說我 跳5階前 加了一步， 跳到了 第6階上。然后直接 跳最后一階。

跟?

跳6階的 跳法? 中，然后直接跳到最后一階 是重復的 跳法。

?

第一種是 5階跳法 中間多跳1階，然后跳最后。

第二種是原本的6階跳法，直接跳 最后。

因此，這種思維是錯誤的。

我的想法：

感覺這個題目形容起來不是很清晰，看的話估計也不是很明白，這個題目給我的感覺就是，多一階臺階后，其實中間臺階怎么跳法不介意，第一步只能多在 n-1階跳法的 最前面，跟最后面， 也就是 2*(n-1)階跳法。

無論怎么加在中間，肯定是 有重復的跳法。

?

?