牛客が階段を登る

タイトル

リンク:階段を登るソース:牛客網
子供が階段を上がっています.階段にはn段の階段があります.子供は一度に1階、2階、3階に上がることができます.子供がどのように2階に上がるかを計算する方法を実現してください.オーバーフロー防止のため、結果Mod 1000000007を
正の整数int nを指定すると、2階に上がる方法の数を表す数を返します.nが100000以下であることを保証する.
テストサンプル1:

1

 ：1

テストサンプル2:

3

 ：4

試験例3:

4

 ：7

問題を読んで心を動かせ!この問題は見たことがある.まあ、確かに似たような問題がありますが、子供が階段を登っているのも、その子が一度に1歩か2歩移動しているだけです.この子は1、2、3歩です.

ぶんせき

考え方:実は考えが同じです.再帰で書くことができます.もし子供が最初の一歩が1歩歩いたら、まだ(n-1)階段が残っていて、もし子供が最初の一歩が2歩歩いたら、まだ(n-2)階段が残っていて、もし子供が最初の一歩が3歩歩いたら、まだ(n-3)階段が残っています.子供の第一歩はこの3つの状況で、残りの歩き方は実はこの3つを合わせています!だから再帰はこのように書くことができます:あなた(再帰)が簡潔であることに損はありません

// 
    public static int getCount(int n){
     
        if(n == 1){
     
            return 1;
        }else if(n == 2){
     
            return 2;
        }else if(n == 3){
     
            return 4;
        }else {
     
            return getCount(n-1)+getCount(n-2)+getCount(n-3);
        }
    }

しかし、再帰計算が遅いのも有名だ.だから私たちは非再帰に変えなければなりません.また、データオーバーフローを回避する必要があります.
1歩か2歩歩ける子供の問題をしたことがある人は、その子供の歩き方がフィボナッチ数列であることを発見することができます.
かいだん
歩き方
1
1
2
2
3
3
4
5
5
8
…
…
同じように、3歩歩ける子供の歩き方をまとめてみましょう.
かいだん
歩き方
1
1
2
2
3
4
4
7
5
13
…
…
発見しましたか:3歩歩ける子供の歩き方も、フィボナッチ数列のような数列です.フィボナッチ数列は前の2つの要素を加算して3番目に得られた.この数列は最初の3つを加算して4つ目になります.このように...
コードを書いてみましょう

// 
    public static int getCounts(int n){
     
        if(n == 1){
     
            return 1;
        }else if(n == 2){
     
            return 2;
        }else if(n == 3){
     
            return 4;
        }else {
     
            int first = 1;
            int second = 2;
            int third = 4;
            int forth = 0;
            while (n - 3 > 0) {
     
                forth = ((first + second)%1000000007+third%1000000007)%1000000007;
                first = second;
                second = third;
                third = forth;
                n--;
            }
            return forth;
        }
    }

ここで難しいのは、

forth = ((first + second)%1000000007+third%1000000007)%1000000007

データオーバーフローを防ぐため、問題は結果mod 100000007を要求する

forth = (first + second+third)%1000000007;

でもこれで溢れ出すので、再改造が必要!牛客評論区はこの言葉の解釈を発見し、インターネットで調べたところ、(a+b)%c==(a%c+b%c)%cなので、(first+second+third)%100000007を上記に変更することができます.
これでメインアルゴリズムが書き終わります.次は通過コードです.

コード#コード#

import java.util.*;

public class GoUpstairs {
     
    // 
    public static int getCounts(int n){
     
        if(n == 1){
     
            return 1;
        }else if(n == 2){
     
            return 2;
        }else if(n == 3){
     
            return 4;
        }else {
     
            int first = 1;
            int second = 2;
            int third = 4;
            int forth = 0;
            while (n - 3 > 0) {
     
                forth = ((first + second)%1000000007+third%1000000007)%1000000007;
                first = second;
                second = third;
                third = forth;
                n--;
            }
            return forth;
        }
    }
    public int countWays(int n) {
     
        // write code here
        return getCounts(n);
    }
}