This is a very simple problem, given a number, we need to find the number of ways to reach it using increments of 1 and 2, given consecutive 1s not allowed.

Go through these two problems first to get the complete idea:

Consider this example to understand the problem clearly:

4
4 can be arrived as:
2+2
1+2+1
1+1+2 (not allowed)

5
5 can be arrived as:
2+2+1
1+2+2
2+1+2
1+2+1+1 (not allowed)

From the example the number of ways to reach 4 and 5 with elimination of possible solutions with consecutive 1s is 2 and 3 respectively.

The solution is actually the same of the previous one(consecutive 2s not allowed) with minor changes. Only dynamic programming approach is given here as the brute force approach is the same as the dynamic one without the memorisation table.

Go through the above article which we have covered in detail. In this article, we will see how we can change to solve our current problem: Number of ways to reach a number or a score in a game using increments of 1 and 2 (consecutive 1s are not allowed).

Dynamic Programming approach

Since the brute force algorithm couldn't handle the substructure problem very well, we are using a 2D array to store the intermediate results, to avoid calculating the same subproblem over and over.

Just the previous one, we will have a variable flag that has the information if we've previously used a 1 or no. Initialized to 0 which means we haven't used a 1 yet, in that case we use a 1 and change flag=1, simultaneously we use and 2, with flag value unchanged. count() takes 'n' which is the target number as the parameter and res is the answer.

if (flag == 0 && n > 0) 
        res = res + count(n - 1, 1) + count(n - 2, 0); 
  
else if(n > 0)
        res = res + count(n - 2, 0);

We use a dp[][] to store information about the states, i.e whether we've calculated that subproblem already or no. Therefore the array is initialized to -1, and its value gets updated based on the solution to the subproblem. And we calculate the solution to the subproblem only if it's value is -1, else we use the available information.

Implementation of dynamic approach

#include<iostream>
using namespace std;

int count(int n, int flag){
 
 if(dp[n][flag]!=-1)
   return dp[n][flag];
 
  if(n==0) return 1;
  int res=0;  
  if (flag == 0 && n > 0) 
        res = res + count(n - 1, 1) + count(n - 2, 0); 
  
else if(n > 0)
        res = res + count(n - 2, 0);  
 return dp[n][flag]=res;
}

int main(){
    int n=4;
    int dp[n+1][2];
    memeset(dp,-1,sizeof(dp));
    cout<<count(n,0);
}

Output

2

Changes made to this algorithm

The only change that is made here is the change of flag value. if we take one step, flag=1, if we take 2 steps at a time flag=0;