C++で隣接する2つが黄色にならないように2つの色で階段をペイントする方法

n個の階段と2色（赤と黄色）があり、これらの階段をペイントすることができます。私たちの仕事は、2つの連続するステップが黄色にならないように、階段をペイントできる方法の数を数えることです。

問題を理解するために例を見てみましょう

入力

3

出力

5

説明

The ways in which stairs can be painted are YRY, RYR, YRR, RRY, RRR. here R denotes red color, Y denotes yellow color.

この問題を解決するために、階段をペイントする方法の数を見てみましょう。

N =1、ways（1）=2：R、Y

N =2、ways（2）=3：RY、YR、RR

N =3、ways（3）=5：RYR、YRY、RRY、YRR、RRR

N =4、ways（4）=8：YRYR、RYRY、RYRR、YRRY、YRRR、RRYR、RRRR、RRRY。

したがって、これらのケースから、これは最初の要素として2、2番目の要素として3で始まるフィボナッチ数列であると導き出すことができます。

ロジックの動作を説明するプログラム

例

#include <iostream>
using namespace std;
int colorSteps(int n) {
   int first = 2;
   int next = 3;
   for (int i = 3; i <= n; i++) {
      next = first + next;
      first = next - first;
   }
   return next;
}
int main(){
   int n = 6;
   cout<<"Number of ways to color "<<n<<" steps is "<<colorSteps(n);
   return 0;
}

出力

Number of ways to color 6 steps is 21