Advanced DP

#Topic: LCS (Longest Common Subsequence) — dp table + sequence reconstruction
#Time: O(n × m)   Space: O(n × m) → can be optimized to O(m)

def lcs_length(a: str, b: str) -> int:
    """Returns only the length of LCS.

    Time:  O(n × m)
    Space: O(n × m)"""
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[n][m]


def lcs_reconstruct(a: str, b: str) -> str:
    """Restores the LCS sequence (backtracking).

    Time:  O(n × m) dp + O(n + m) backtracking
    Space: O(n × m)"""
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    #Backtracking: from (n, m) to (0, 0)
    result: list[str] = []
    i, j = n, m
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            result.append(a[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return "".join(reversed(result))


def lcs_space_optimized(a: str, b: str) -> int:
    """Space-optimized LCS (rolling array — length only).

    Time:  O(n × m)
    Space: O(m) — keep only the current row and the previous row"""
    n, m = len(a), len(b)
    prev = [0] * (m + 1)

    for i in range(1, n + 1):
        curr = [0] * (m + 1)
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev = curr

    return prev[m]


def print_dp_table(a: str, b: str) -> None:
    """Visualizes the LCS dp table."""
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    header = f"{'':>4}" + "".join(f"{'':>3}{ch}" for ch in " " + b)
    print(header)
    for i, row in enumerate(dp):
        label = " " if i == 0 else a[i - 1]
        print(f"{label:>4}" + "".join(f"{v:>4}" for v in row))


#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
    print("=== LCS Table Visualization ===")
    a, b = "ABCBDAB", "BDCAB"
    print(f"A = {a}")
    print(f"B = {b}")
    print()
    print_dp_table(a, b)

    print(f"LCS length: {lcs_length(a, b)}")
    print(f"LCS sequence: '{lcs_reconstruct(a, b)}'")
    print(f"Space O(m): {lcs_space_optimized(a, b)}")

    print("=== Additional Tests ===")
    test_cases = [
        ("AGGTAB", "GXTXAYB"),
        ("ABCDEF", "ABCDEF"),
        ("ABC", "DEF"),
        ("", "ABC"),
        ("A", "A"),
    ]
    for s1, s2 in test_cases:
        length = lcs_length(s1, s2)
        seq = lcs_reconstruct(s1, s2)
        print(f"LCS('{s1}', '{s2}') = {length}, sequence='{seq}'")

    print("=== LCS Application: diff (character insertion/deletion) ===")
    def diff_count(s1: str, s2: str) -> tuple[int, int]:
        """Calculates edit distance using LCS (insertions + deletions only)."""
        lcs = lcs_length(s1, s2)
        deletions = len(s1) - lcs
        insertions = len(s2) - lcs
        return deletions, insertions

    pairs = [("kitten", "sitting"), ("sunday", "saturday")]
    for s1, s2 in pairs:
        d, i = diff_count(s1, s2)
        print(f"'{s1}' → '{s2}': deletions={d}, insertions={i}")

#Topic: LIS (Longest Increasing Subsequence)
# O(n²) DP  vs  O(n log n) patience sorting (bisect)

from bisect import bisect_left


def lis_dp(arr: list[int]) -> tuple[int, list[int]]:
    """LIS O(n²) DP.

    dp[i] = length of LIS ending with arr[i]
    dp[i] = max(dp[j] + 1) for j < i if arr[j] < arr[i]

    Time:  O(n²)
    Space: O(n)

    Returns:
        (length, actual LIS sequence)"""
    n = len(arr)
    if n == 0:
        return 0, []

    dp = [1] * n
    parent = [-1] * n   #For Backtracking

    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                parent[i] = j

    max_len = max(dp)
    last_idx = dp.index(max_len)

    #Backtracking
    lis: list[int] = []
    idx = last_idx
    while idx != -1:
        lis.append(arr[idx])
        idx = parent[idx]

    return max_len, list(reversed(lis))


def lis_nlogn(arr: list[int]) -> int:
    """LIS O(n log n) — patience sorting + bisect.

    tails[k] = the smallest last element of an increasing subsequence of length k+1

    For each element:
      - Find the first position in tails that is greater than or equal to arr[i] (bisect_left)
      - Place arr[i] in that position (append if not found → length increases by 1)

    Time:  O(n log n)
    Space: O(n)"""
    tails: list[int] = []

    for x in arr:
        pos = bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x

    return len(tails)


def lis_nlogn_reconstruct(arr: list[int]) -> tuple[int, list[int]]:
    """LIS O(n log n) — including actual sequence reconstruction.

    Time:  O(n log n)
    Space: O(n)"""
    n = len(arr)
    if n == 0:
        return 0, []

    tails: list[int] = []
    indices: list[int] = []    #Original index of the element placed in tails
    predecessor: list[int] = [-1] * n  #Backtracking

    for i, x in enumerate(arr):
        pos = bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
            indices.append(i)
        else:
            tails[pos] = x
            indices[pos] = i

        if pos > 0:
            predecessor[i] = indices[pos - 1]

    #Backtracking
    lis: list[int] = []
    idx = indices[-1]
    while idx != -1:
        lis.append(arr[idx])
        idx = predecessor[idx]

    return len(tails), list(reversed(lis))


def count_lis(arr: list[int]) -> tuple[int, int]:
    """Compute both the length of LIS and the number of LIS.

    Time:  O(n²)
    Space: O(n)

    Returns:
        (maximum length, number of LIS of that length)"""
    n = len(arr)
    if n == 0:
        return 0, 0

    dp = [1] * n      #Length
    cnt = [1] * n     #Count

    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    cnt[i] = cnt[j]
                elif dp[j] + 1 == dp[i]:
                    cnt[i] += cnt[j]

    max_len = max(dp)
    total = sum(cnt[i] for i in range(n) if dp[i] == max_len)
    return max_len, total


#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
    arr = [10, 9, 2, 5, 3, 7, 101, 18]

    print("=== Comparing LIS results ===")
    print(f"Array: {arr}")

    length_dp, seq_dp = lis_dp(arr)
    print(f"O(n²) DP:    Length={length_dp}, Sequence={seq_dp}")

    length_nl = lis_nlogn(arr)
    print(f"O(nlogn):     Length={length_nl}")

    length_rec, seq_rec = lis_nlogn_reconstruct(arr)
    print(f"O(nlogn)+Restoration: Length={length_rec}, Sequence={seq_rec}")

    print("=== Visualization of patience sorting process ===")
    tails: list[int] = []
    for x in arr:
        pos = bisect_left(tails, x)
        action = "append" if pos == len(tails) else f"replace[{pos}]"
        before = tails[:]
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
        print(f"Element {x:3d}: {before} → {action}({x}) → {tails}")
    print(f"LIS length: {len(tails)}")

    print("=== Testing various arrays ===")
    test_arrays = [
        [3, 10, 2, 1, 20],
        [3, 2],
        [50, 3, 10, 7, 40, 80],
        [1, 2, 3, 4, 5],
        [5, 4, 3, 2, 1],
    ]
    for a in test_arrays:
        l_dp, s_dp = lis_dp(a)
        l_nl = lis_nlogn(a)
        length, count = count_lis(a)
        print(f"{a}: Length={l_dp}, Sequence={s_dp}, Count={count}")
        assert l_dp == l_nl, f"Mismatch: {l_dp} vs {l_nl}"
    print("All results match ✓")

#Topic: 0/1 Knapsack Problem
#Time: O(n × W)   Space: O(n × W) → O(W) Optimization

from typing import NamedTuple


class Item(NamedTuple):
    weight: int
    value: int
    name: str = ""


def knapsack_2d(items: list[Item], capacity: int) -> int:
    """0/1 Knapsack 2D DP.

    dp[i][w] = The maximum value when considering the first i items and filling up to capacity w

    Recurrence:
      If we do not take item i: dp[i][w] = dp[i-1][w]
      If we take item i:         dp[i][w] = dp[i-1][w - items[i].weight] + items[i].value
                                 (if items[i].weight ≤ w)

    Time:  O(n × W)
    Space: O(n × W)"""
    n = len(items)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        item = items[i - 1]
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]   #Not taken
            if item.weight <= w:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - item.weight] + item.value)

    return dp[n][capacity]


def knapsack_1d(items: list[Item], capacity: int) -> int:
    """0/1 Knapsack 1D DP (space optimization).

    Key: iterate w in reverse (capacity → weight)
    → Prevents using the same item twice

    Time:  O(n × W)
    Space: O(W)"""
    dp = [0] * (capacity + 1)

    for item in items:
        #Reverse! (capacity → item.weight)
        for w in range(capacity, item.weight - 1, -1):
            dp[w] = max(dp[w], dp[w - item.weight] + item.value)

    return dp[capacity]


def knapsack_reconstruct(items: list[Item], capacity: int) -> tuple[int, list[Item]]:
    """0/1 Knapsack — Recovering the actually selected items.

    Time:  O(n × W)
    Space: O(n × W)"""
    n = len(items)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        item = items[i - 1]
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]
            if item.weight <= w:
                val = dp[i - 1][w - item.weight] + item.value
                if val > dp[i][w]:
                    dp[i][w] = val

    #Backtracking
    selected: list[Item] = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:
            selected.append(items[i - 1])
            w -= items[i - 1].weight

    return dp[n][capacity], list(reversed(selected))


def unbounded_knapsack(items: list[Item], capacity: int) -> int:
    """Unbounded Knapsack (each item can be used multiple times).

    1D DP, forward iteration (reverse iteration would be 0/1 Knapsack)

    Time:  O(n × W)
    Space: O(W)"""
    dp = [0] * (capacity + 1)

    for w in range(1, capacity + 1):
        for item in items:
            if item.weight <= w:
                dp[w] = max(dp[w], dp[w - item.weight] + item.value)

    return dp[capacity]


#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
    items = [
        Item(2, 6, "Apple"),
        Item(2, 10, "Banana"),
        Item(3, 12, "Grape"),
        Item(1, 4, "Strawberry"),
        Item(4, 15, "Watermelon"),
    ]
    capacity = 7

    print("=== Knapsack Problem ===")
    print(f"Capacity: {capacity}")
    print(f"{'Item':>6} | {'Weight':>4} | {'Value':>4}")
    print("-" * 22)
    for item in items:
        print(f"{item.name:>6} | {item.weight:>4} | {item.value:>4}")

    ans_2d = knapsack_2d(items, capacity)
    ans_1d = knapsack_1d(items, capacity)
    max_val, selected = knapsack_reconstruct(items, capacity)

    print(f"\nMaximum Value (2D): {ans_2d}")
    print(f"Maximum Value (1D): {ans_1d}")
    print(f"Selected Items: {[i.name for i in selected]}")
    print(f"Total Weight: {sum(i.weight for i in selected)}")
    assert ans_2d == ans_1d == max_val

    print("\n=== 0/1 vs Unbounded Knapsack Comparison ===")
    simple_items = [Item(1, 1, "A"), Item(2, 4, "B"), Item(3, 5, "C")]
    for cap in range(1, 8):
        v01 = knapsack_1d(simple_items, cap)
        vub = unbounded_knapsack(simple_items, cap)
        print(f"Capacity={cap}: 0/1={v01}, Unbounded={vub}")

    print("\n=== dp Table Visualization (Small Example) ===")
    small_items = [Item(2, 6, "A"), Item(2, 10, "B"), Item(3, 12, "C")]
    W = 5
    n = len(small_items)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        item = small_items[i - 1]
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]
            if item.weight <= w:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - item.weight] + item.value)

    header = f"{'Item':>5}" + "".join(f"{j:>5}" for j in range(W + 1))
    print(f"  {header}")
    labels = ["(None)"] + [f"Item{i}({small_items[i-1].name})" for i in range(1, n+1)]
    for i, row in enumerate(dp):
        print(f"  {labels[i]:>12}" + "".join(f"{v:>5}" for v in row))

#Topic: Matrix Chain Multiplication Order Optimization (Matrix Chain Multiplication)
# Time: O(n³)   Space: O(n²)


def matrix_chain_order(dims: list[int]) -> tuple[int, list[list[int]]]:
    """Minimum number of operations for matrix chain multiplication.

    dims[i-1] × dims[i] = size of the i-th matrix
    Example: dims = [30, 35, 15, 5, 10, 20, 25]
        Matrix 0: 30×35, Matrix 1: 35×15, ..., Matrix 5: 20×25

    dp[i][j] = minimum number of multiplications for multiplying matrices i through j
    dp[i][j] = min(dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1])
               for k in range(i, j)

    Time:  O(n³)
    Space: O(n²)

    Returns:
        (minimum number of operations, table s with splitting information)"""
    n = len(dims) - 1   #Number of matrices
    INF = float("inf")

    #dp[i][j]: Minimum cost to multiply matrices i~j
    dp = [[0] * n for _ in range(n)]
    #s[i][j]: Optimal split point
    s = [[0] * n for _ in range(n)]

    #Subproblems in order of length l = 2, 3, ..., n
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = INF

            for k in range(i, j):
                cost = (
                    dp[i][k]
                    + dp[k + 1][j]
                    + dims[i] * dims[k + 1] * dims[j + 1]
                )
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    s[i][j] = k

    return dp[0][n - 1], s


def reconstruct_order(s: list[list[int]], i: int, j: int) -> str:
    """Restoration of optimal parenthesization.

    Time:  O(n)
    Space: O(n) recursive stack"""
    if i == j:
        return f"A{i}"
    k = s[i][j]
    left = reconstruct_order(s, i, k)
    right = reconstruct_order(s, k + 1, j)
    return f"({left} × {right})"


def naive_count_multiplications(
    order: list[int], dims: list[int]
) -> int:
    """Calculate the actual number of multiplications when multiplying matrices in the given order (for verification).

    order: sequence of matrix indices
    dims: list of matrix dimensions"""
    #Rows/columns of the current result matrix
    current_rows = dims[order[0]]
    current_cols = dims[order[0] + 1]
    total = 0

    for idx in order[1:]:
        next_rows = dims[idx]
        next_cols = dims[idx + 1]
        total += current_rows * current_cols * next_cols
        current_cols = next_cols

    return total


#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
    #Textbook example: dims = [30, 35, 15, 5, 10, 20, 25]
    #Matrices A0(30×35), A1(35×15), A2(15×5), A3(5×10), A4(10×20), A5(20×25)
    dims = [30, 35, 15, 5, 10, 20, 25]
    n = len(dims) - 1

    print("=== Matrix Information ===")
    for i in range(n):
        print(f"  A{i}: {dims[i]} × {dims[i+1]}")

    min_cost, s = matrix_chain_order(dims)
    order_str = reconstruct_order(s, 0, n - 1)

    print(f"\nMinimum number of operations: {min_cost:,}")
    print(f"Optimal order: {order_str}")

    print("\n=== dp Table ===")
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = min_cost if (i == 0 and j == n - 1) else 0

    #Recalculation
    dp2, s2 = matrix_chain_order(dims)
    print(f"{'':>8}" + "".join(f"{'A'+str(j):>10}" for j in range(n)))
    dp_table = [[0] * n for _ in range(n)]
    INF = float("inf")
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp_table[i][j] = INF
            for k in range(i, j):
                cost = dp_table[i][k] + dp_table[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
                if cost < dp_table[i][j]:
                    dp_table[i][j] = cost
    for i in range(n):
        row_str = f"{'A'+str(i):>8}"
        for j in range(n):
            val = dp_table[i][j] if dp_table[i][j] != INF else 0
            row_str += f"{val:>10,}"
        print(row_str)

    print("\n=== Small Example ===")
    small = [10, 30, 5, 60]
    cost, s_small = matrix_chain_order(small)
    print(f"dims={small}")
    print(f"Minimum cost: {cost}, Order: {reconstruct_order(s_small, 0, 2)}")
    print(f"  (A0×A1)×A2: {10*30*60 + 10*5*60}")  #Incorrect order (for reference only)
    print(f"  A0×(A1×A2): {30*5*60 + 10*30*60}")