Advanced Dynamic Programming

from functools import lru_cache

# ── LONGEST PALINDROMIC SUBSEQUENCE ── O(n^2) ───────────────────────
def lps(X):
    """
    Length of longest palindromic subsequence of string X.
    Uses interval DP: L[i][j] = LPS of X[i..j].
    Bottom-up: fill by increasing interval length.
    """
    n = len(X)
    # L[i][j] = LPS length of X[i..j]
    L = [[0]*n for _ in range(n)]

    # Base case: single characters
    for i in range(n):
        L[i][i] = 1

    # Fill for increasing lengths 2, 3, ..., n
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            if X[i] == X[j]:
                L[i][j] = 2 + (L[i+1][j-1] if length > 2 else 0)
            else:
                L[i][j] = max(L[i+1][j], L[i][j-1])
    return L[0][n-1]

def lps_reconstruct(X):
    """Reconstruct the actual LPS string."""
    n = len(X)
    L = [[0]*n for _ in range(n)]
    for i in range(n): L[i][i] = 1
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            if X[i] == X[j]:
                L[i][j] = 2 + (L[i+1][j-1] if length > 2 else 0)
            else:
                L[i][j] = max(L[i+1][j], L[i][j-1])

    # Traceback
    result, i, j = [], 0, n-1
    while i <= j:
        if i == j:
            result.append(X[i]); break
        if X[i] == X[j]:
            result.append(X[i])
            i += 1; j -= 1
        elif L[i+1][j] > L[i][j-1]:
            i += 1
        else:
            j -= 1
    left = result
    right = result[:-1][::-1] if L[0][n-1] % 2 == 1 else result[::-1]
    return ''.join(left + right)


# ── OPTIMAL BINARY SEARCH TREE ── O(n^3) ────────────────────────────
def optimal_bst(weights):
    """
    Minimum expected search cost BST for keys 1..n with given weights.
    Returns (cost, root_table) where root_table[i][j] = optimal root for keys i..j.
    Cost e[i][j] = min over roots r of: e[i][r-1] + e[r+1][j] + W(i,j).
    O(n^3) time, O(n^2) space.
    """
    n = len(weights)
    W = weights[:]          # W[i] = weight of key i (0-indexed)

    # Prefix sums for W(i,j) = sum(W[i..j])
    prefix = [0] * (n+1)
    for i in range(n): prefix[i+1] = prefix[i] + W[i]
    def range_sum(i, j): return prefix[j+1] - prefix[i]

    # e[i][j] = optimal cost for keys i..j (0-indexed)
    e    = [[0.0]*n for _ in range(n)]
    root = [[0]*n   for _ in range(n)]

    # Base cases: single keys
    for i in range(n):
        e[i][i]    = W[i]
        root[i][i] = i

    # Fill for increasing lengths
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            Wij = range_sum(i, j)
            e[i][j] = float('inf')
            for r in range(i, j+1):
                cost = (e[i][r-1] if r > i else 0) + \
                       (e[r+1][j] if r < j else 0) + Wij
                if cost < e[i][j]:
                    e[i][j] = cost
                    root[i][j] = r
    return e[0][n-1], root

# Example from lecture: w = [1, 10, 8, 9]
cost, roots = optimal_bst([1, 10, 8, 9])
print(f"Optimal BST cost: {cost}")          # 49
print(f"Root of full tree: key {roots[0][3]+1}")  # key 3 (weight=8)

# ── ALTERNATING COIN GAME ── O(n^2) ─────────────────────────────────
def coin_game(V):
    """
    V: list of coin values (length must be even).
    Returns maximum value first player can guarantee.
    V(i,j) = max value current player earns from coins V[i..j].
    Opponent plays optimally (min), we play optimally (max).
    """
    n = len(V)
    dp = [[0]*n for _ in range(n)]

    # Base cases
    for i in range(n):
        dp[i][i] = V[i]
    for i in range(n-1):
        dp[i][i+1] = max(V[i], V[i+1])

    # Fill for increasing lengths (even only, but we compute all)
    for length in range(3, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            # Take V[i]: opponent sees [i+1..j], picks better for them
            take_left  = V[i] + min(
                dp[i+2][j] if i+2 <= j else 0,     # opp takes V[i+1]
                dp[i+1][j-1] if i+1 <= j-1 else 0  # opp takes V[j]
            )
            # Take V[j]: opponent sees [i..j-1], picks better for them
            take_right = V[j] + min(
                dp[i+1][j-1] if i+1 <= j-1 else 0, # opp takes V[i]
                dp[i][j-2] if i <= j-2 else 0       # opp takes V[j-1]
            )
            dp[i][j] = max(take_left, take_right)
    return dp[0][n-1]


# ── BOOLEAN PARENTHESISATION ── O(n^3) ──────────────────────────────
def bool_paren(symbols, operators):
    """
    Count ways to parenthesise symbols[0..n-1] with operators[0..n-2]
    such that the expression evaluates to True.
    symbols: list of booleans (True/False)
    operators: list of 'AND', 'OR', 'XOR'
    Returns count (may be exponential).
    """
    n = len(symbols)
    T = [[0]*n for _ in range(n)]  # T[i][j]: ways to True
    F = [[0]*n for _ in range(n)]  # F[i][j]: ways to False

    # Base cases
    for i in range(n):
        T[i][i] = 1 if symbols[i] else 0
        F[i][i] = 0 if symbols[i] else 1

    # Fill for increasing lengths
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):     # split at operator k (between k and k+1)
                op  = operators[k]
                tl, fl = T[i][k], F[i][k]
                tr, fr = T[k+1][j], F[k+1][j]
                tot_l, tot_r = tl+fl, tr+fr
                if op == 'AND':
                    T[i][j] += tl * tr
                    F[i][j] += tot_l*tot_r - tl*tr
                elif op == 'OR':
                    T[i][j] += tot_l*tot_r - fl*fr
                    F[i][j] += fl * fr
                elif op == 'XOR':
                    T[i][j] += tl*fr + fl*tr
                    F[i][j] += tl*tr + fl*fr
    return T[0][n-1]

# Example: True AND False XOR True
syms = [True, False, True]
ops  = ['AND', 'XOR']
print(bool_paren(syms, ops))   # 2

# ── RECTANGULAR BLOCKS TOWER ── O(n^2) ──────────────────────────────
def max_tower(blocks):
    """
    blocks: list of (length, width, height) tuples.
    Returns maximum achievable tower height.
    Block i can sit on block j only if l_i <= l_j AND w_i <= w_j.
    DP: H[i] = max height of tower with block i on top.
    H[i] = h_i + max(H[j] for j < i if l_j >= l_i and w_j >= w_i)
    """
    # Sort descending by (length, width)
    blocks = sorted(blocks, key=lambda b: (-b[0], -b[1]))
    n = len(blocks)
    H = [b[2] for b in blocks]    # H[i] starts as just its own height

    for i in range(1, n):
        li, wi, hi = blocks[i]
        for j in range(i):
            lj, wj, _ = blocks[j]
            if lj >= li and wj >= wi:  # block j can support block i
                H[i] = max(H[i], hi + H[j])

    return max(H)

# Example
blocks = [(4,3,2), (1,1,5), (3,2,3), (2,2,4)]
print(max_tower(blocks))   # 11 = (4,3,2)+(3,2,3)+(2,2,4)+(1,1,5) impossible;
                           # actual: (4,3,2) -> (3,2,3) -> (2,2,4) = 9


# ── MAKE CHANGE ── O(mN) pseudo-polynomial ───────────────────────────
def min_coins(coins, N):
    """
    Minimum coins to make N cents using coin denominations in `coins`.
    C[p] = min C[p - S_i] + 1 for all S_i <= p.
    O(m * N) time, O(N) space. Pseudo-polynomial (not polynomial in bits of N).
    """
    INF = float('inf')
    C = [INF] * (N + 1)
    C[0] = 0
    for p in range(1, N + 1):
        for s in coins:
            if s <= p and C[p - s] + 1 < C[p]:
                C[p] = C[p - s] + 1
    return C[N] if C[N] != INF else -1

# Reconstruct which coins were used
def min_coins_with_path(coins, N):
    INF = float('inf')
    C    = [INF] * (N + 1)
    last = [-1]  * (N + 1)
    C[0] = 0
    for p in range(1, N + 1):
        for s in coins:
            if s <= p and C[p-s]+1 < C[p]:
                C[p] = C[p-s]+1; last[p] = s
    # Traceback
    path, p = [], N
    while p > 0:
        path.append(last[p]); p -= last[p]
    return C[N], path

cost, used = min_coins_with_path([1, 5, 10, 25], 41)
print(f"Coins needed: {cost}, using: {used}")  # 4 coins: [25,10,5,1]