Dynamic Programming 11

Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1’s.

Problem link :- click here

Code

import java.util.Arrays;
import java.util.Scanner;

public class DynamicProgramming_11
{
	//Recursion and Memoization
	static int noConsecutive1s(int n, int[] memo)
	{
		if(memo[n] != 0)
			return memo[n];
		
		if(n == 1)
		{
			memo[n] = 2;
			return 2;	// 0  &  1
		}
		if(n == 2)
		{
			memo[n] = 3;
			return 3;	// 00  &  01  &  10
		}
		
		int start_10 = noConsecutive1s(n-2, memo);
		int start_0   = noConsecutive1s(n-1, memo);
		
		return start_10 + start_0;
	}
	
	//DP
	static int noConsecutive1s1(int n)
	{
		int arr[] = new int[n+1];
		
		Arrays.fill(arr, 0);
		
		arr[1] = 2;
		arr[2] = 3;
		
		for(int i=3; i<=n; i++)
			arr[i] = arr[i-1] + arr[i-2];
		
		return arr[n];
	}

	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);
		
		System.out.print("Enter the size of the binary string : ");
		int n = s.nextInt();
//		int memo[] = new int[n+1];
		
		int ans = noConsecutive1s1(n);
		System.out.println("\n\n" + ans);
		
		s.close();
	}

}