Monica and Gaming Obsession

Monica is a legendary player of badminton. She is going to participate in a Knockout - Badminton tournament with n - 1 other players.

The organising committee are still deciding the order in which the games will happen and which team player is going to play with who. But they have already stated one rule:

Two player standoff if and only if the absolute difference of number of games played is atmost one.

So one thing is clear that both players had to attain victory in all of their matches in order to continue participating in the tournament.

Since the tournament has not started yet and Monica was being bored sitting and making faces she thought what will be the highest number of matches she will have to play if she is going to win the tournament. As you know Monica is poor in mathematics she asks for your help to solve the problem.(Of course she thinks you can do it !!)

Example:

Input:  n = 10
Output: 4

Approach

C++

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

const int N = 1001;
long long dp[N];

int main()
{

    long long n = 10;

    dp[0] = 1;
    dp[1] = 2;
    int i = 1;
    while (dp[i] <= n)
    {
        i++;
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    cout << i - 1;

    return 0;
}