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]