Count of binary strings without consecutive 1’s

Given a positive integer N, find the count of distinct binary strings of length N that have no consecutive 1’s. For example,

Input:
N = 2
Output:
3.
Explanation:
There are 3 possible strings: 00, 01, 10
N=3
There are 5 possible strings: 000, 001, 010, 100,101

Thought process to find binary strings with consecutive 1s

This problem is an easier variation of digit DP problem. Since these are binary strings for every position in the string there are just two choices: 0 and 1. To form a string of length N, at any position –

  1. We can choose 0 and then for the next position we again have two choices.
  2. We can choose 1 but then for the next position we cannot choose 1 as we don’t want consecutive 1’s in the string. So once we choose 1, we are also setting next position to 0.

So in case (a), we set 0 at current position and the problem then reduces to count the number of strings having length N-1 with the given condition.

And in case (b), we set 1 at current position and 0 at next position, hence the problem reduces to count the number of strings having length N-2 with the given condition.

With this we can write

Count(n) = Count(n-1) + Count(n-2)

Does this formula ring a bell? Yes, it’s the same one that is is used to find Fibonacci numbers.

As Count(1) = 2, Count(2) = 3, Count(3) = 5, ……
and Fib(1) = 1,  Fib(2) = 1, Fib(3) = 2, Fib(3) = 3, Fib(4) = 5, ……

Hence we can observe that-
Count(n) = Fib(n+2)

Using the explanation for DP approach and the implementation in Find Nth Fibonacci number problem:

#include <iostream>
#include <vector>
using namespace std;

long long int fib(int N)
{
    vector<long long int> DPVec(N+1, 0);
    DPVec[1] = 1; DPVec[2] = 1;
    for (int i=3; i<=N; ++i)
    {
          DPVec[i] = DPVec[i-1] + DPVec[i-2];
    }
   return DPVec[N];
}

long long int Cnt_strings(int N)
{
    return fib(N+2);
}

int main()
{
    int n = 3;
    cout<<Cnt_strings(n)<<endl;
    return 0;
}
public class Count_Strings
{
    static int fib(int N)
    {
        int DPArr[] = new int[N+1];
        DPArr[1] = 1; DPArr[2] = 1;
        for (int i=3; i&lt;=N; ++i)
        {
            DPArr[i] = DPArr[i-1] + DPArr[i-2];
        }
        return DPArr[N];
    }
       
    static int Cnt_strings(int N)
    {
        return fib(N+2);
    }
    
    public static void main (String[] args) 
    {
	int n = 4;
	int num_strings = Cnt_strings(n);
	System.out.println(num_strings);
    }
}
The time complexity of the implementation is O(n) and space complexity is also O(n)

Climbing the staircase

We have to climb a staircase and it takes N steps to reach the top. Given that we can climb 1 or 2 steps at a time, in how many possible ways can we climb to the top? For example, let N = 3 i.e. there are 3 steps to climb. In this case, we can reach the top by:
– 1 step, 1 step, 1 step
– 1 step, 2 steps
– 2 steps, 1 step
So there are 3 possible ways to reach the top if we can take {1, 2} steps at a time.

How can we think of a solution? At the position that we are currently standing (be it start of the staircase or in the middle somewhere on the staircase) we have two choices, we can either climb 1 step or we can climb 2 steps. This also means that we reached our current position on the staircase by climbing either 1 step or 2 steps, i.e. if we are at step say x we reached here by climbing from either (x-1)th step or (x-2)th step. To actually find in how many ways we can reach x, we need to know in how many ways we reached x-1 and x-2 in the first place and then add them to find the number of ways to reach x. To make this easier to understand let’s look at some examples.

Consider we are at step 0 (ground) and the staircase has just 1 step, so the number of ways to reach the top is:
1st way : [0🡪1] => take 1 step and we reach the top.
Climbing staircase

Consider the staircase has 2 steps, so the number of ways to reach the top is:
1st way: [0🡪1🡪2] => take 1 step at a time and climb one by one step to reach the top
2nd way: [0🡪2] => take 2 steps and reach the top
Climbing staircase

Consider the staircase has 3 steps, so the number of ways to reach the top is:
now consider we are actually at the top at step 3, according to our thoughts above we can reach step 3 (x) either by from step 2 (x-1) or from step 1 (x-2). Let’s consider the case for step 1 (x-2) first: We already know number of ways to reach step 1 and that is 1 =>
1) [0🡪1]: using this we reach step 3 => [0🡪1🡪3].

Similarly, we already know the number of ways to reach step 2 and that are 2 =>
1) [0🡪1🡪2]: using this we get another way to reach step 3 => [0🡪1🡪2🡪3]
2) [0🡪2]: using this we get another way to reach step 3 => [0🡪2🡪3].

So finally we have our three ways to reach step 3:
[0🡪1🡪3], [0🡪1🡪2🡪3], and [0🡪2🡪3].

Notice that we just added 3 to already known paths for step 1 and step 2.

Consider the staircase has 4 steps, so the number of ways to reach the top is:
number of ways to reach step 2 (x-2) + number of ways to reach step 3 (x-1) = 5
From step 2: [0🡪1🡪2🡪4], [0🡪2🡪4]
From step 3: [0🡪1🡪3🡪4], [0🡪1🡪2🡪3🡪4] and [0🡪2🡪3🡪4].

So from the examples we understand that: total_ways(n) = total_ways(n-1) + total_ways(n-2).

Note that this means this problem has optimal substructure (i.e. an optimal solution can be constructed from optimal solutions of subproblems).
This formula is similar to the one we used to find Nth Fibonacci number. Actually total_ways(n) = findNthFib(n+1).

Notice it is (N+1)th Fibonacci number and not Nth, that’s because of the bases cases from where we start our calculations. Consider a case that the staircase has 0 steps to climb and we start from the ground (i.e. step 0), so in this case we argue that there’s only 1 way to reach the top i.e. [0].
With this argument:
total_ways(0) = 1, total_ways(1) = 1…
findNthFib(0) = 0, findNthFib(1) = 1, findNthFib(2) = 1…
and hence the formula total_ways(n) = findNthFib(n+1).

There’s another variation of this problem where the number of steps that can be taken at a time is not limited to just {1, 2}.

Total possible ways to climb a staircase (variation 2)

We have to climb a staircase and it takes N steps to reach the top. Given that we can climb 1 or 2 or 3 steps at a time, in how many possible ways can we climb to the top?
For example, let n = 3 i.e. there are 3 steps to climb. In this case, we can reach the top by:
– 1 step, 1 step, 1 step
– 1 step, 2 steps
– 2 steps, 1 step
– 3 steps
So there are 4 possible ways to reach the top of a staircase of 3 steps if we can take {1, 2, 3} steps at a time

Similar to the approach taken above, we can reach our current position on staircase by climbing either 1 step or 2 steps or 3 steps, i.e. if we are at step say x we reached here by climbing from either x-1th step or x-2th step or x-3th step. So to actually find in how many ways we can reach x, we need to know in how many ways we reached x-1, x-2 and x-3 in the first place and then adding them will give number of ways to reach x.

total_ways(n) = total_ways(n-1) + total_ways(n-2) + total_ways(n-3)
This formula maps to a recursive solution:

long long int findTotalWays (int n)
{
    if(n == 0 || n == 1) return 1;
   if(n == 2) return 2;
    return findTotalWays(n-1) + findTotalWays(n-2) + findTotalWays(n-3);
}
 
int main(void) 
{
    int N = 5;
    long long int total_ways = findTotalWays(N);
    printf("%lld", total_ways);
    return 0;
}

But this solution is not feasible as it has exponential time complexity. To find the reason behind this let’s look at the function call tree:

As we can see here that the subproblems such as total_ways(3) and total_ways(2) are calculated repeatedly. This means that the subproblems are overlapping.
As the two properties required for using dynamic programming : optimal substructure and overlapping subproblems hold true, we can use DP for this problem.

int main(void) 
{
    int N = 5;
    vector<long long int> DPVec(N+1, 0);
    DPVec[0] = 1; DPVec[1] = 1; DPVec[2] = 2;
    for (int i=3; i<=N; ++i)
    {
          DPVec[i] = DPVec[i-1] + DPVec[i-2] + DPVec[i-3];
    }
    printf("%lld", DPVec[N]);
    return 0;
}

The time and space complexity of the implementation is O(n).

Total possible ways to climb a staircase (variation 3)

We have to climb a staircase and it takes N steps to reach the top. Given that we can climb 1 or 3 or 5 steps at a time, in how many possible ways can we climb to the top? To generalize we can be given any set of the allowed number of steps that can be taken at a time and we have to find the number of possible ways to climb to the top?

Keeping in mind the above described approach, the formula again here is: total_ways(n) = total_ways(n-1) + total_ways(n-3) + total_ways(n-5) As negative step does not make any sense, we will recur for non-negative steps only.

long long int findTotalWays (int n, vector<int> &Step_Set)
{
    if(n == 0) return 1;
   long long int total_ways = 0;
   for(int i=0; i<Step_Set.size();++i)
   {
        if ((n – Step_Set[i]) >= 0)
             total_ways += findTotalWays(n- Step_Set[i], Step_Set);
   }
    return total_ways;
}
 
int main(void) 
{
    int N = 5;
    vector<int> Step_Set{1, 3, 5};
    long long int total_ways = findTotalWays(N, Step_Set);
    printf("%lld", total_ways);
    return 0;
}

Dynamic programming solution for the problem

int main(void) 
{
    int N = 5;
    vector<int> Step_Set{1, 3, 5};
    vector<long long int> DPVec(N+1, 0);
    DPVec[0] = 1;
    for (int i=1; i<=N; ++i)
    {
         for (int j=0; j<Step_Set.size(); ++j)
        {
               if ((i – Step_Set[j]) >= 0)
              {
                   DPVec[i] += DPVec[i- Step_Set[j]];
              }
        }
    }
    printf("%lld", DPVec[N]);
    return 0;
}

The time is O(m*n) and space complexity: O(m + n) where m is size of the set of allowed steps and n is the number of steps in the staircase. These implementations work in general for any set of allowed steps.

This article is contributed by Bhushan Aggrawal.

Fibonacci series and dynamic programming

Find nth Fibonacci number

Given a Fibonacci series: 1, 1, 2, 3, 5, 8, 13 … which is defined as fib(n) = fib(n-1) + fib(n-2), find Nth number in this series. For example, 5th Fibonacci number is 5. 11th Fibonacci number is 89.

By definition of the Fibonacci series, it is clear that every number in the series is a sum of the last two numbers in the series. So to find nth number we just need to know (n-1)th and (n-2)th number, once we find these two numbers just adding them will give us the answer.

fib(n) = fib(n-1) + fib(n-2)

But how do we find these numbers? We keep taking the same approach for (n-1)th and (n-2)th number, i.e.
fib(n-1) = fib(n-2) + fib(n-3) and
fib(n-2) = fib(n-3) + fib(n-4)

We stop only when we hit fib(1) = 1 and fib(2) = 1.
This shows this problem has optimal substructure (i.e. an optimal solution can be constructed from optimal solutions of subproblems).

Recursive approach

The explanation/formula given above maps to simple recursion:

long long int findNthFib(int n)
{
    if(n == 1 || n == 2) return 1;
    return findNthFib(n-1) + findNthFib(n-2);
}
 
int main(void) 
{
    int N = 11;
    long long int NthFib = findNthFib(N);
    printf("%lld", NthFib);
    return 0;
}

The recursive code looks extremely simple. This is one of the advantages of recursion, it saves the efforts of writing lots of code.
Everything looks fine and we are happy with our solution until we try to find 40th or so Fibonacci number using this approach. This implementation takes over 3 secs to find 43rd Fibonacci number and the execution time increases exponentially with increasing inputs.
To find the reason behind such high runtime let’s have a look at the recursive function call tree:
dynamic programming fibonacci

In this example of finding 6th Fibonacci number, subproblems such as fib(4) and fib(3) are calculated repeatedly. Imagine how many such repeated calculations would be there when we use this implementation for finding 43rd Fibonacci number!! Hence the time 3secs.

Our recursive algorithm for this problem solves the same subproblem over and over rather than always generating new subproblems. These are called overlapping subproblems. As the two properties required for using Dynamic Programming: optimal substructure and overlapping subproblems hold, we can use DP for this problem. But before jumping to a dynamic programming solution, there’s another way to resolve the issue of overlapping subproblems in a recursive approach: Memoised approach. Let’s have a look at it first.

Memoised approach for Fibonacci series

To avoid repeated calculation in the recursive approach, we can store the base cases and the results of each fib() call in an array. The code would look like this:

long long int findNthFib(int n, vector<long long int> &memo)
{
    if (memo[n] != 0)
         return memo[n];
    memo[n] = findNthFib(n-1, memo) + findNthFib(n-2, memo);
    return memo[n];
}
 
int main(void) 
{
    int N = 43;
    vector<long long int> memo(N+1, 0);
    memo[1] = 1; memo[2] = 1;
    long long int NthFib = findNthFib(N, memo);
    printf("%lld", NthFib);
    return 0;
}

With the memoized approach the function call tree looks like this:
Fibonacci memoization

By memoizing intermediate results, we avoid repeated calculations. The time complexity of the memoized approach is O(n) and Space complexity is O(n). In both the approaches described above, observe that we took a top-down approach, i.e. we started from n and went down till 1.
Unlike recursion, Dynamic Programming uses a bottom-up approach, let’s see how it’s done in DP.

Dynamic Programming approach

In DP we start calculating from the bottom and move up towards the final solution. For this problem we first find 1st Fibonacci number, then 2nd, then 3rd and so on until Nth Fibonacci number. To aid this approach we use an array/vector where we will store the intermediate results while we move towards the final solution. The code looks like this:

int main(void) 
{
    int N = 43;
    vector<long long int> DPVec(N+1, 0);
    DPVec[1] = 1; DPVec[2] = 1;
    for (int i=3; i<=N; ++i)
    {
          DPVec[i] = DPVec[i-1] + DPVec[i-2];
    }
    printf("%lld", DPVec[N]);
    return 0;
}

Time complexity: O(n) Space complexity: O(n)
The space complexity of the DP code can be reduced by storing just the last two results instead of every result and in this way array/vector is no more required.
Moreover, there are other solutions for finding Nth Fibonacci number in O(log N) time using matrices and in O(1) constant time using the golden ratio, but this article is limited to DP approach.

This article is contributed by Bhushan Aggrawal.