Q:

Step count problem | Find the number of possible combinations to reach the final step

You are trying to climb on a staircase. There are N number of steps. You can only climb one or two steps at one time. Now you have to find out the number of possible combinations to reach the final step.

```Input:
First-line contains T Testcases,
T no. of lines along with the step count(N).

E.g.
3
4
5
6

Output:
Print the number of possible valid steps
to reach the last step.
```

Example

```T = 3

Input:
4
Output:
5

Input:
5
Output:
8

Input:
6
Output:
13```

To find out the possible combination to reach the last step is a problem of combination. We are using the Dynamic programming approach to solve it with less time complexity.

To solve this problem, we will follow these steps,

1. We need an array of size equals the number of steps N.
2. We initialize the first step with the value one.
3. Initialize the second step with two because you can take two steps to reach the second step or you can directly move to the second step. Therefore, in the second step there in two possibilities.
4. For the steps those are greater than the 2nd there is two possibilities,
1. To reach the ith step, we can go from the (i-1) step.
2. To reach the ith step, we can go from the (i-2) step.
```
Let f(i)= no. Of possible combination to reach the ith step.
f(i)= f(i-1) +f(i-2)

```

C++ Implementation:

``````#include <bits/stdc++.h>
using namespace std;

int count(int num)
{
int arr[num];
arr[0] = 1;
arr[1] = 2;
for (int i = 2; i < num; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[num - 1];
}

int main()
{
int t;

cout << "Testcase : ";
cin >> t;

while (t--) {
int num;

cout << "Enter the Steps : ";
cin >> num;

cout << "Step Count : " << count(num) << endl;
}

return 0;
}``````

Output

```Testcase : 3
Enter the Steps : 5
Step Count : 8
Enter the Steps : 10
Step Count : 89
Enter the Steps : 7
Step Count : 21```