C++プログラミング例題変態ステップのアルゴリズム分析

問題の説明
1匹のカエルは一度に1段の階段を飛び上がることもできるし、2段も飛び上がることもできるし...n段も飛び上がることもできる.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
もんだいぶんせき
f(n)をn段階段を飛び上がる飛び方数とする.このカエルがn段の階段を飛び上がると、最初のジャンプにはn種類のジャンプ法があり、それぞれ:1段、2段...n段を跳びます.第1ジャンプを踊った後、次の旅を完成したのは以下の状況である:第1ジャンプ1級、次はf(n-1)種のジャンプ法が第n級に達する;第1跳跳2级,然后有f(n-2)种跳法到第n级;...第1ジャンプはn級で、直接旅を終えた.
したがって,1つのn段にジャンプしたステップを,f(n)=f(n−1)+f(n−2)+f(1)+1のうちf(n−1)が1段目にジャンプした場合,f(n−2)が2段目にジャンプした場合,...,f(1)がn−1段目にジャンプした場合,1が1段目にジャンプした場合に分解することができる.また、f(n-1)=f(n-2)+f(n-3)+…+f(1)+1は、f(n-1)中のf(n-2)+…+f(1)+1をf(n-1)で置換し、f(n)=2 f(n-1)を得ることができる.すなわち、f(n)は2を比とする等比数列である.
さらに、f(1)=1,f(2)=2を列挙することで、f(n)=2 n-1を押し出すことができる.
コード実装
アルゴリズムを読めば、コードは簡単で辛いです.一言でできます.

class Solution {
public:
    int jumpFloorII(int number) {
        return pow(2,number-1);
    }
};