Consecutive 1's not allowed
Dynamic Programming
medium
Score: 30
Given a positive integer n, count all possible distinct binary strings of length n such that there are no consecutive 1’s. Return the answer modulo 10^9 + 7
Input Format
First Parameter: A single positive integer n
Output
Return a single integer
Example 1
Input:
n = 3
Output: 5
Explanation: 5 strings are (000,
001, 010, 100, 101).
Example 2
Input:
N = 2
Output: 3
Explanation: 3 strings are
(00,01,10).
Constraints
1 ≤ n ≤ 10^5- Expected Time Complexity:
O(n) - Expected Space Complexity:
O(n)