ステップ問題+変態ステップ問題解法(ダイナミックプランニング再帰+非再帰)

一、階段跳び問題
一つの階段に全部でn級があります.一度に1級踊れば、2級も踊れます.全部でどれだけの総ジャンプ法があるかを求めて、そしてアルゴリズムの時間の複雑さを分析します.
タイトルの記述では、これがFibonacci数列であることがよくわかります.
再帰的な実装:

unsigned long long solution(int stageNum)
{
    //      
    if(stageNum <= 0)
        return 0;
    else if(1 == stageNum)
        return 1;
    else if(2 == stageNum)
        return 2;

    return solution(stageNum - 1) + solution(stageNum - 2);
}

これは最低レベルのやり方で、時間は入力規模の指数レベルです.計算キャッシュを追加して再帰速度を向上させることができます.
トップダウンのダイナミックプランニングを採用します.

//         
unsigned long long solution(int stageNum)
{
    static unsigned long long Counter[101] = {0};
    if(0 != Counter[stageNum])
        return Counter[stageNum];

    //      
    if(stageNum <= 0)
        return 0;
    else if(1 == stageNum)
        return Counter[1] = 1;
    else if(2 == stageNum)
        return Counter[2] = 2;

    Counter[stageNum] = solution(stageNum - 1) + solution(stageNum - 2);
    return Counter[stageNum];
}

このアルゴリズムは線形時間複雑度の結果を得ることができる.
非再帰的実装(反復的実装):
//ボトムアップダイナミックプランニング

//         
unsigned long long solution(int number)
{
    //     number    100
    static unsigned long long Counter[101] = {0};
    Counter[1] = 1;
    Counter[2] = 2;
    static int calculatedIndex = 2;

    if(number <= calculatedIndex)
        return Counter[number];

    //      
    if(number > 100)
        number = 100;

    for(int i = calculatedIndex + 1; i <= number; i++)
    {
        Counter[i] = Counter[i - 1] + Counter[i - 2];
    }
    calculatedIndex = number;
    return Counter[number];
}

二、変態階段問題
一つの階段に全部でn級があります.一度に1級踊れるなら、2級も踊れます.n級も踊れます.全部でどれだけの総ジャンプ法があるかを求めて、そしてアルゴリズムの時間の複雑さを分析します.
解析:fib(n)を用いてn段の階段を飛び上がるジャンプ数を表す.定義に従うと、Fib(0)は必ず0にする必要があります.そうしないと意味がありません.ただし、Fib(0)=1を設定します.n=0は特殊な場合であり,以下の解析から分かるように,強制令Fib(0)=1が有利である.ps.Fib(0)は私たちの解題には影響しませんが、次の分析理解に影響します.
n=1の場合、1次ジャンプ:Fib(1)=1のみである.
n=2の場合,1次ジャンプと2次ジャンプ:Fib(2)=2;
ここまでは、普通に階段を跳ぶのと同じです.
n=3の場合、3種類のジャンプ方式があり、初めて1階を飛び出した後、Fib(3-1)種類のジャンプ法に対応する.1回目の2次ジャンプ後、Fib(3-2)種のジャンプ法に対応する.初めて3階を飛び出した後、このジャンプしかありません.Fib(3) = Fib(2) + Fib(1)+ 1 = Fib(2) + Fib(1) + Fib(0) = 4;
n=4の場合、4つの方式がある:第1回は1階を飛び出して、Fib(4-1)種類のジャンプ法に対応する;第1回は2階を飛び出して、Fib(4-2)種類のジャンプ法に対応します;第1回は3階を飛び出して、Fib(4-3)種類のジャンプ法に対応します;初めて4階を飛び出したのは、このジャンプしかありません.したがって,Fib(4)=Fib(4−1)+Fib(4−2)+Fib(4−3)+1=Fib(4−1)+Fib(4−2)+Fib(4−3)+Fib(4−4)種のジャンプ法である.
n=nの場合、n種類のジャンプ方式があり、初めて1階を飛び出した後、後ろにはFib(n-1)のジャンプ法がある.1回目の2次ジャンプ後、後ろにはFib(n-2)の中ジャンプが・・・・・・初めてn階を飛び出した後、後ろにはFib(n-n)でジャンプする方法もあります.Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+..........+Fib(n-n) = Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-1).
上記の解析により、一般式を得ました.
                 Fib(n) =  Fib(0)+Fib(1)+Fib(2)+.......+ Fib(n-2) + Fib(n-1)
したがって、Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-2)
2つの式は、Fib(n)−Fib(n−1)=Fib(n−1)===="Fib(n)=2*Fib(n−1)n>=3に減算される.
これが我々に必要な繰返し式である:Fib(n)=2*Fib(n-1)n>=3
//ボトムアップのダイナミックプランニング

//         
//  N  
unsigned long long solution(int number)
{
    //     number    100
    static unsigned long long Counter[101] = {0};
    Counter[0] = 1;
    Counter[1] = 1;
    Counter[2] = 2;
    static int calculatedIndex = 2;

    if(number <= calculatedIndex)
        return Counter[number];

    //      
    if(number > 100)
        number = 100;

    for(int i = calculatedIndex + 1; i <= number; i++)
    {
        Counter[i] = 2 * Counter[i - 1];
    }
    calculatedIndex = number;
    return Counter[number];
}