階段を登る

3227 ワード

今日はクライミング階段の問題を解決する方法を紹介します.
これが問題です

私は、この問題の解決をよりよく理解するために木を造るつもりです.
つの階段の上に登ることができるどのように多くの異なる方法で決定しましょう.
私は、私たちが取ることができるステップの数に基づいて木に枝を追加するつもりです.この問題では、1ステップまたは2ステップを取ることができます.我々が1歩をとるならば、我々は3つのより多くのステップに登らなければなりません.我々は2ステップを取る場合は、2つのステップが残っている.ベースケースに到達するまで分岐を続けます.
  • 我々は0のステップを持っているとき、どのように多くの方法が登るには?1つの方法があります-我々は、ちょうど登りません.
  • 我々は1つのステップを持っているとき、どのように多くの方法が登るには?1つの方法があります-ちょうどその一歩に登ること.
  • 階段を登る方法の合計数を計算するには、まずどのように多くの方法は、各ステップを取得するには、下から始まる方法を把握する必要があります.私たちは一緒に各ステップの方法の数を追加し、4ステップ階段を登るには5つの方法の合計があることがわかります.

    今この問題の解決策はその問題の合計であることがわかります.我々の場合では、4ステップ階段を登る方法の合計数は、3ステップ階段と2ステップ階段を登る合計方法の合計です.これに基づいて書くことができます.
    Numranges Way ( 4 )= Numstrichow Way ( 3 )+ Numhorn Way ( 2 )
    n個のステップについては、式は次のとおりです.
    NumHunseの方法( n )= numstricway ( n - 1 )+ numstricway ( n - 2 )
    これは実際にFibonacciシーケンスです.Fibonacciシーケンスの各番号は、0と1から始まる2つの前のものの合計です.
    0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 ,…
    FIB ( n )= FIB ( n )−1 ) + FIB ( n )−2).
    解決策は次のようになります.
    var climbStairs = function(n) {
        if (n == 1 || n == 0) return 1 // our base cases
    
        let first = 1;
        let second = 2;
    
        for (let i = 3; i <= n; i++) {
            let third = first + second;
            first = second;
            second = third;
        }
        return second;
    
    };