登山階段問題:それを解決する方法とFibonacci数が関連している理由

今日のアルゴリズムはClimbing Stairs problem :

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.

例えば、入力が2(階段の2つの階段がある)ならば、2つの異なった方法がトップに上がるためにあります.あなたは一度に1つのステップを登ることができるか、一度に両方のステップを登ることができます.

これは、再帰とmemoizationとダイナミックプログラミングを含むそれを解決する多くの方法があるそれらの問題の1つです.このポストでは、フィボナッチ数がどのようなものであるかを説明します.

フィボナッチ数

何ですか。

Fibonacci数(また、Fibonacci系列として知られています)は、再帰方程式によって定義される一連の数です:

Fn = Fn-1 + Fn-2

シーケンスはf 0＝0、f 1＝1で始まる.F 2＝F 1＋F 0＝1＋0であるため、F 2＝1となる.F 3＝F 2＋F 1＝1＋1であるのでF 3＝2となる.シーケンスは無限に続きます:0、1、1、2、3、5、8、13、21、34.
あなたはFibonacci番号についての詳細を読むことができますhere .

なぜFibonacci数は階段問題に関連するのか？

階段問題の予想される出力のいくつかの例を見てみましょう.n = 0から始めることができます.階段は階段が0である.この階段を登る方法は0ですので、N = 0のとき、出力は0です.

n＝1の場合、階段は1ステップである.この階段を登る方法は1つありますので、N = 1の場合は出力＝1となります.

n＝2の場合、階段は2ステップである.私たちは一度に1または2階段を登ることができるので、この階段を登るには2つの方法があります.したがって、n＝2のとき、出力＝2となる.

n＝3の場合、階段は3ステップである.この階段を登ることができる3つの方法があります.

これはN = 4 (出力= 5 )のときに行うことができます.

... とn = 5 ( output = 8 ).

出力内の任意のパターンに注意してください.

我々は、我々の出力でFibonacciシーケンスを見ることができます!Nをインクリメントするたびに、階段を登る方法の数は前の2つの方法の合計です.それは、私たちがnに到達するまで、階段の問題を解決することができます.

アルゴリズムの解決

出力のパターンを認識したので、アルゴリズムを解決できます.開始するには、いくつかのベースケースを書き出す必要があります.nが0、1、2の場合、階段0、1、および2(その順序で)を登る方法の数は- nがそれらの数の1つであるなら、Nを返すことができます.

function climbStairs3(n) {
  if (n < 3) return n;
  //...
}

つの定数を初期化する必要がありますfirst と呼ばれるsecond . 我々は設定によって開始しますfirst を返します.second 2に等しい.我々は、我々が現在の数に加えるためにこれらの数を使っていて、彼らを変え続けます.

function climbStairs3(n) {
  if (n < 3) return n;
  let first = 1;
  let second = 2;
  //...
}

今、ナンバー2から始まり、我々が到達するまでn , 私たちは一度に1つの数値をインクリメントするためのループを持つことができます.forループ内で、新しい変数を開始しますcurrent これはfirst and second . そして、我々は移動することができますfirst 等しいsecond , and second 等しいcurrent .
forループが終了したら、私たちはsecond 番号は.

function climbStairs3(n) {
  if (n < 3) return n;
  let first = 1;
  let second = 2;
  for (let i = 2; i < n; i++) {
    const current = first + second;
    first = second;
    second = current;
  }

  return second;
}

--
あなたが質問やこれを解決する他の方法がある場合は私に知らせてください!