Count Valid Binary Strings

You are given a non-negative integer n representing the length of a binary string. Your task is to calculate the number of valid binary strings of length n that do not contain consecutive '1's. A binary string contains only the characters '0' and '1'.

The problem can be solved using a dynamic programming approach. Let dp[i][0] denote the number of valid strings of length i ending with '0' and dp[i][1] denote the number ending with '1'. The recurrence relation is given by:

[ \begin{aligned} dp[i][0] &= dp[i-1][0] + dp[i-1][1], \ dp[i][1] &= dp[i-1][0]. \end{aligned} ]

For n = 0, output is defined to be 0.

Example:
For n = 3, the valid strings are: "000", "001", "010", "100", "101". Hence, the answer is 5.

inputFormat

The input consists of a single non-negative integer n provided via standard input.

outputFormat

Output a single integer representing the number of valid binary strings of length n that do not contain consecutive '1's, printed to standard output.

0

0