模块 2 · 动态规划 与 贪心算法

def matrix_chain_order(p):
    """矩阵连乘最小标量乘法次数，矩阵 A_i 维度为 p[i-1] x p[i]。O(n^3) 时间、O(n^2) 空间。"""
    n = len(p) - 1
    if n <= 1:
        return 0
    m = [[0] * (n + 1) for _ in range(n + 1)]
    for length in range(2, n + 1):  # 链长 l 从 2 到 n 对角线推进
        for i in range(1, n - length + 2):
            j = i + length - 1
            m[i][j] = min(
                m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
                for k in range(i, j)
            )
    return m[1][n]

def lcs_length(a, b):
    """LCS 长度。O(len(a)*len(b)) 时间，O(len(b)) 空间。"""
    prev = [0] * (len(b) + 1)
    for ca in a:
        dp = [0] * (len(b) + 1)
        for j, cb in enumerate(b, 1):
            dp[j] = prev[j - 1] + 1 if ca == cb else max(prev[j], dp[j - 1])
        prev = dp
    return prev[-1]

def max_subarray(nums):
    """最大非空连续子段和（Kadane 算法）。O(n) 时间、O(1) 空间。"""
    if not nums:
        raise ValueError('数组不能为空')
    cur = best = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

def knapsack_01(weights, values, capacity):
    """正整数重量的 0-1 背包。O(n*capacity) 伪多项式时间。"""
    if (
        len(weights) != len(values)
        or not isinstance(capacity, int)
        or capacity < 0
        or any(not isinstance(w, int) or w <= 0 for w in weights)
    ):
        raise ValueError('输入非法：重量须正整数、容量须非负整数')
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):  # 倒序防止一个物品被重复选
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]

def optimal_bst(p, q):
    """最优二叉查找树期望代价，p[0..n-1] 为实结点概率，q[0..n] 为伪结点概率。O(n^3) 时间。"""
    n = len(p)
    e = [[0.0] * (n + 2) for _ in range(n + 2)]
    w = [[0.0] * (n + 2) for _ in range(n + 2)]
    for i in range(1, n + 2):
        e[i][i - 1] = w[i][i - 1] = q[i - 1]
    for length in range(1, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            w[i][j] = w[i][j - 1] + p[j - 1] + q[j]
            e[i][j] = min(
                e[i][r - 1] + e[r + 1][j] + w[i][j]
                for r in range(i, j + 1)
            )
    return e[1][n]

def activity_selection(intervals):
    """最多不重叠区间 [start,end)。O(n log n) 时间。"""
    if any(t < s for s, t in intervals):
        raise ValueError('结束早于开始')
    ans, last = [], float('-inf')
    for s, t in sorted(intervals, key=lambda x: x[1]):
        if s >= last:
            ans.append((s, t))
            last = t
    return ans

def weighted_interval_scheduling(intervals):
    """带权活动安排 (start, end, weight) 最大总权重。O(n log n) 时间。"""
    if not intervals:
        return 0
    jobs = sorted(intervals, key=lambda x: x[1])
    ends = [j[1] for j in jobs]
    dp = [0] * (len(jobs) + 1)
    for i, (s, _, w) in enumerate(jobs, 1):
        p = bisect_right(ends, s, 0, i - 1)
        dp[i] = max(dp[i - 1], dp[p] + w)
    return dp[-1]

def dijkstra(graph, source):
    """邻接表 (v,weight) 的非负最短路。堆 O((V+E)log V)。"""
    n = len(graph)
    if not 0 <= source < n:
        raise ValueError('源点越界')
    if any(v < 0 or v >= n or w < 0 for edges in graph for v, w in edges):
        raise ValueError('端点越界或存在负权')
    dist = [float('inf')] * n
    dist[source] = 0
    pq = [(0, source)]
    while pq:
        d, u = heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            new = d + w
            if new < dist[v]:
                dist[v] = new
                heappush(pq, (new, v))
    return dist