Count Binary Strings

1. You are given a number n.

2. You are required to print the number of binary strings of length n with no consecutive 0's.

Note: In this problem, you are given a number n. All we need to print is the number of binary strings of length n with no consecutive 0's For example: Sample Input: 3 Sample Output: 5 How 5? We have a total of eight binary numbers for length 3, out of which we have 5 numbers in which there are no consecutive zeros.

Input Format

A number n

Output Format

A number representing the number of binary strings of length n with no consecutive 0's.

Constraints
0 < n <= 45
Sample Input
6
Sample Output
21

Solution:

import java.io.*;

import java.util.*;

public class Main{

public static void main(String[] args) throws Exception {

    // write your code here

    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();

    

    int dp[][] = new int[n+1][2];

    dp[1][0] = 1;

    dp[1][1] = 1;

    

    for(int i=2;i<=n;i++){

        dp[i][0] = dp[i-1][1];

        dp[i][1] = dp[i-1][0] + dp[i-1][1];

    }

    

    System.out.println(dp[n][0]+dp[n][1]);

 }

}