# TCINVW - EDITORIAL

Author: h4wk
Editorialist: qaseem_hasan_

EASY

# PROBLEM:

This question is a standard variation of the Classical Number of ways to reach nth position on a ladder by using only one step or two step.

# QUICK EXPLANATION:

We can compute the sum at every i using the recurrence relation that:
sumAt(i) = sumAt(i-1) + sumAt(i-2)
If observed this relation you would find this is the fibonacci relation. Hence the answer is the Nth fibonacci number.

# SOLUTIONS:

This can be calculated in 2 easy ways: iteration approach or recursive approach.

Editorialist's Solution (iterative)
``````    #include<iostream>
using namespace std;

int main()
{
int n;
scanf("%d",&n);
int fibo[n+1] = {0}; //clear set values to 0

// Assume you're standing at level 1.
fibo[1] = 1; //there are 1 total ways to reach 1st level(actually standing)
fibo[2] = 1; //there are 1 total ways to reach 2nd level(taking one step)

{
fibo[i] = fibo[i-1] + fibo[i-2];

/*fibo[3] = fibo[2] + fibo[1]; i.e. number of ways to reach 3rd step is sum of ways to reach step 2(1 step) and step 1(1 step), that's why fibo[3] = 2
you can either make one jump/step from step 2 or two jumps from step 1.*/
}

printf("%d",fibo[n]); // simple print the accumulation of numbers of ways upto the level n, answer.
}
``````
Editorialist's Solution (recursive)
``````    #include<iostream>
using namespace std;

int fibo(int n){
if(n==0)
return 0;
if(n==1)
return 1;
return fibo(n-1) + fibo(n-2);
}

int main()
{
int n;
cin >> n;

int ans = fibo(n);
cout << ans;
}
``````