"""
Solving problems with Dynamic Programming

Copyright 2020, University of Freiburg

Philipp Schneider <philipp.schneider@cs.uni-freiburg.de>
"""

import sys

sys.setrecursionlimit(10000)


def no_consecutive_ones(n):
    '''
        Returns the number of n-digit binary
        strings without consecutive ones

        Parameter:
            n - positive integer

        Returns:
            positive integer

        Unit-Tests:
            >>> no_consecutive_ones(1)
            2

            >>> no_consecutive_ones(3)
            5

            >>> no_consecutive_ones(5)
            13
    '''
    memo = {}
    return no_consecutive_ones_ending(n, 0, memo)\
        + no_consecutive_ones_ending(n, 1, memo)


def no_consecutive_ones_ending(n, i, memo):
    '''
        Returns the number of n-digit binary strings
        ending on i without consecutive ones

        Parameter:
            n - positive integer
            i - 0 or 1
            memo - dictionary for memoization

        Returns:
            positive integer
    '''

    if (n, i) in memo:
        return memo[(n, i)]

    if i == 0:
        if n == 1:
            a = 1
        else:
            a = no_consecutive_ones_ending(n-1, 0, memo)\
                + no_consecutive_ones_ending(n-1, 1, memo)

        memo[(n, i)] = a
        return a

    else:
        if n == 1:
            a = 1
        else:
            a = no_consecutive_ones_ending(n-1, 0, memo)
        memo[(n, i)] = a
        return a