Dynamic Programming I

# ── TOP-DOWN (memoisation) ────────────────────────────────────────────
def fib_memo(n):
    memo = {}
    def F(i):
        if i < 2: return i          # base cases: F(0)=0, F(1)=1
        if i not in memo:
            memo[i] = F(i-1) + F(i-2)  # relation, computed once
        return memo[i]
    return F(n)

# ── BOTTOM-UP (tabulation) ────────────────────────────────────────────
def fib_dp(n):
    if n < 2: return n
    F = [0] * (n + 1)
    F[0], F[1] = 0, 1               # base cases
    for i in range(2, n + 1):       # topological order: increasing i
        F[i] = F[i-1] + F[i-2]     # relation
    return F[n]                     # original problem

# ── SPACE-OPTIMISED (O(1) extra space) ───────────────────────────────
def fib_opt(n):
    a, b = 0, 1
    for _ in range(n): a, b = b, a + b
    return a
# SRT BOT: subproblems=F(0)..F(n), relation=F(i)=F(i-1)+F(i-2),
# topo=increasing i, bases=F(0),F(1), original=F(n), time=O(n).

def bowl(v):
    """Max score from bowling pins with values v. Θ(n) time."""
    n = len(v)
    # Bottom-up: process suffixes in decreasing order
    B = [0] * (n + 2)              # B[n] = B[n+1] = 0 (base cases)
    for i in reversed(range(n)):
        B[i] = max(
            B[i + 1],                          # skip pin i
            v[i] + B[i + 1],                   # hit pin i alone
            v[i] * v[i + 1] + B[i + 2]         # hit pins i and i+1
            if i + 1 < n else v[i] + B[i + 1]  # guard: no pin i+1
        )
    return B[0]

# Example: v = [-1, 1, 1, 1, 9, 9, 3, -3, -5, 2, 2]
# B(10)=2, B(9)=max(0,2)=2, B(8)=max(2,-5+2,-5*2+2)=2,...
# B(4)=max(B(5), 9+B(5), 9*9+B(6)) = max(9*9+3, ...) = 81+3 = 84... etc.

def lcs(A, B):
    """Length of longest common subsequence of A and B. O(|A|*|B|)."""
    a, b = len(A), len(B)
    # x[i][j] = LCS of A[i:] and B[j:]
    x = [[0] * (b + 1) for _ in range(a + 1)]   # base cases: last row/col = 0
    for i in reversed(range(a)):                 # decreasing i
        for j in reversed(range(b)):             # decreasing j
            if A[i] == B[j]:
                x[i][j] = x[i+1][j+1] + 1       # match: use both
            else:
                x[i][j] = max(x[i+1][j], x[i][j+1])  # skip A[i] or B[j]
    return x[0][0]

# Example: A = "hieroglyphology", B = "michaelangelo"
# lcs(A, B) = 5  (one solution: "hello")

def lcs_string(A, B):
    """Recover the actual LCS string using parent pointers."""
    a, b = len(A), len(B)
    x = [[0]*(b+1) for _ in range(a+1)]
    for i in reversed(range(a)):
        for j in reversed(range(b)):
            if A[i] == B[j]: x[i][j] = x[i+1][j+1] + 1
            else: x[i][j] = max(x[i+1][j], x[i][j+1])
    # Traceback
    result, i, j = [], 0, 0
    while i < a and j < b:
        if A[i] == B[j]: result.append(A[i]); i += 1; j += 1
        elif x[i+1][j] >= x[i][j+1]: i += 1
        else: j += 1
    return ''.join(result)

def lis(A):
    """Length of longest strictly increasing subsequence. O(n²)."""
    n = len(A)
    x = [1] * n                    # x[i] = LIS starting at A[i], min length 1
    for i in reversed(range(n)):
        for j in range(i + 1, n):
            if A[j] > A[i]:        # A[j] can follow A[i]
                x[i] = max(x[i], 1 + x[j])
    return max(x) if x else 0      # original: try all starting points

# Example: A = "carbohydrate" (treat as list of chars)
# or numerically: A = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
# LIS = [1, 4, 5, 9] or [1, 2, 6] etc., length depends on input

# O(n log n) version uses patience sorting (bisect module):
import bisect
def lis_fast(A):
    tails = []                     # tails[k] = smallest tail of IS of length k+1
    for a in A:
        pos = bisect.bisect_left(tails, a)
        if pos == len(tails): tails.append(a)
        else: tails[pos] = a
    return len(tails)