def fib(n):
    """Return the nth Fibonacci number.

    >>> fib(0)
    0
    >>> fib(1)
    1
    >>> fib(6)
    8
    >>> fib(30)
    832040
    """
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 2) + fib(n - 1)


def fib_memo(n):
    """Return the nth Fibonacci number. Memoized.

    >>> fib(0)
    0
    >>> fib(1)
    1
    >>> fib(6)
    8
    >>> fib(30)
    832040
    """
    cache = {}
    cache[0], cache[1] = 0, 1

    def mem(n):
        if n not in cache:
            cache[n] = mem(n - 2) + mem(n - 1)
        return cache[n]

    return mem(n)


def fib_iter(n):
    """Return the nth Fibonacci number. Iterative.

    >>> fib_iter(0)
    0
    >>> fib_iter(1)
    1
    >>> fib_iter(6)
    8
    >>> fib_iter(30)
    832040
    """
    i = 0
    curr, next = 0, 1
    while i < n:
        curr, next = next, curr + next
        i += 1
    return curr


def lcs_len(word1, word2):
    """
    Recursive implementation of longest common subsequence (len). No DP.

    >>> lcs_len("dog", "")
    0
    >>> lcs_len("dog", "cat")
    0
    >>> lcs_len("louis", "gucci")  # ui
    2
    >>> lcs_len("romeo", "othello")  # oeo
    3
    >>> lcs_len("beamer", "bentley")  # bee
    3
    """
    if word1 == "" or word2 == "":
        return 0
    elif word1[0] == word2[0]:
        return 1 + lcs_len(word1[1:], word2[1:])
    else:
        return max(lcs_len(word1, word2[1:]), lcs_len(word1[1:], word2))


def lcs_len_index(word1, word2):
    """
    Recursive implementation of longest common subsequence (len). No string
    slicing.

    >>> lcs_len_index("dog", "")
    0
    >>> lcs_len_index("dog", "cat")
    0
    >>> lcs_len_index("louis", "gucci")  # ui
    2
    >>> lcs_len_index("romeo", "othello")  # oeo
    3
    >>> lcs_len_index("beamer", "bentley")  # bee
    3
    """
    def helper(i, j):
        if i == len(word1) or j == len(word2):
            return 0
        elif word1[i] == word2[j]:
            return 1 + helper(i + 1, j + 1)
        else:
            return max(helper(i, j + 1), helper(i + 1, j))

    return helper(0, 0)


def lcs_len_memo(word1, word2):
    """
    Memoized implementation for longest common subsequence (len).

    >>> lcs_len_memo("dog", "")
    0
    >>> lcs_len_memo("dog", "cat")
    0
    >>> lcs_len_memo("louis", "gucci")  # ui
    2
    >>> lcs_len_memo("romeo", "othello")  # oeo
    3
    >>> lcs_len_memo("beamer", "bentley")  # bee
    3
    """
    cache = {}

    def helper(i, j):
        if (i, j) in cache:
            return cache[(i, j)]

        if i == len(word1) or j == len(word2):
            cache[(i, j)] = 0
        elif word1[i] == word2[j]:
            cache[(i, j)] = 1 + helper(i + 1, j + 1)
        else:
            cache[(i, j)] = max(helper(i, j + 1), helper(i + 1, j))
        return cache[(i, j)]

    return helper(0, 0)


def lcs_len_dp(word1, word2):
    """
    DP implementation of longest common subsequence (len).

    >>> lcs_len_dp("dog", "")
    0
    >>> lcs_len_dp("dog", "cat")
    0
    >>> lcs_len_dp("louis", "gucci")
    2
    >>> lcs_len_dp("romeo", "othello")
    3
    >>> lcs_len_dp("beamer", "bentley")  # bee
    3
    """
    len_word1 = len(word1)
    len_word2 = len(word2)
    table = []
    for i in range(len_word2 + 1):              # initialization
        table.append([0] * (len_word1 + 1))
    i = len_word1 - 1
    while i >= 0:
        j = len_word2 - 1
        while j >= 0:
            if word1[i] == word2[j]:
                table[j][i] = 1 + table[j + 1][i + 1]
            else:
                table[j][i] = max(table[j + 1][i], table[j][i + 1])
            j -= 1
        i -= 1
    return table[0][0]


def lcs_len_dp_opt(word1, word2):
    """
    DP implementation of longest common subsequence (len). Remove old columns.

    >>> lcs_len_dp_opt("dog", "")
    0
    >>> lcs_len_dp_opt("dog", "cat")
    0
    >>> lcs_len_dp_opt("louis", "gucci")  # ui
    2
    >>> lcs_len_dp_opt("romeo", "othello")  # oeo
    3
    >>> lcs_len_dp_opt("beamer", "bentley")  # bee
    3
    """
    if len(word1) > len(word2):
        word1, word2 = word2, word1

    empty_column1 = [[0 for _ in range(len(word1) + 1)]]
    empty_column2 = [[0 for _ in range(len(word1) + 1)]]
    columns = empty_column1 + empty_column2
    i, j = len(word1), len(word2) - 1
    while j >= 0:
        while i >= 0:
            if i == len(word1):
                columns[0][i] = 0
            elif word1[i] == word2[j]:
                columns[0][i] = 1 + columns[1][i + 1]
            else:
                columns[0][i] = max(columns[0][i + 1], columns[1][i])
            i -= 1
        columns.pop(1)
        columns.insert(0, [0 for _ in range(len(word1) + 1)])
        i = len(word1)
        j -= 1
    return columns[1][0]