动态规划与贪心

from functools import lru_cache


# 版本 1：朴素递归。直接照搬定义。
# 复杂度 O(2^n)：同一个 f(k) 沿不同路径被重复展开。
def fib_naive(n: int) -> int:
    if n < 2:                       # 边界：f(0)=0, f(1)=1
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)


# 版本 2：记忆化（自顶向下）。给版本 1 加一层缓存。
# 每个 f(k) 只真正计算一次，命中缓存直接返回 ⇒ O(n) 时间、O(n) 空间。
@lru_cache(maxsize=None)            # 缓存即"备忘录"，结构与版本 1 完全一致
def fib_memo(n: int) -> int:
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)


# 版本 3：递推（自底向上）。把递归翻成填表，从边界顺着算到 n。
# 只需保留最近两个值 ⇒ O(n) 时间、O(1) 空间。
def fib_iter(n: int) -> int:
    if n < 2:
        return n
    prev, cur = 0, 1                # prev=f(0), cur=f(1)
    for _ in range(2, n + 1):       # 转移：新值 = 前两个之和
        prev, cur = cur, prev + cur
    return cur


if __name__ == "__main__":
    assert fib_naive(10) == 55
    assert fib_memo(50) == 12586269025      # 朴素版在 n=50 会卡死
    assert fib_iter(50) == 12586269025
    print("ok")

def knapsack_2d(weights: list[int], values: list[int], cap: int) -> int:
    """二维 DP。dp[i][c] = 前 i 件、容量 c 上限下的最大价值。O(n*cap) 时间与空间。"""
    n = len(weights)
    dp = [[0] * (cap + 1) for _ in range(n + 1)]   # 边界：第 0 行全为 0
    for i in range(1, n + 1):
        wi, vi = weights[i - 1], values[i - 1]     # 第 i 件物品（下标从 0）
        for c in range(cap + 1):
            dp[i][c] = dp[i - 1][c]                 # 不选第 i 件
            if c >= wi:                              # 容量够才能选
                dp[i][c] = max(dp[i][c], dp[i - 1][c - wi] + vi)
    return dp[n][cap]


def knapsack_1d(weights: list[int], values: list[int], cap: int) -> int:
    """一维压缩。只保留一行，容量逆序遍历。O(n*cap) 时间、O(cap) 空间。"""
    dp = [0] * (cap + 1)
    for wi, vi in zip(weights, values):
        for c in range(cap, wi - 1, -1):            # 逆序：见下方"想一想"
            dp[c] = max(dp[c], dp[c - wi] + vi)
    return dp[cap]


if __name__ == "__main__":
    w = [2, 3, 4, 5]
    v = [3, 4, 5, 6]
    assert knapsack_2d(w, v, 8) == 10   # 选物品 (w=3,v=4) + (w=5,v=6)
    assert knapsack_1d(w, v, 8) == 10
    print("ok")

from bisect import bisect_left


def lis_dp(nums: list[int]) -> int:
    """O(n^2) DP。dp[i] = 以 nums[i] 结尾的最长递增子序列长度。"""
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n                          # 边界：每个元素自成长度 1
    for i in range(n):
        for j in range(i):                # 枚举所有更靠前的 j
            if nums[j] < nums[i]:         # 能接在 j 后面（严格递增）
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)                        # 答案在全表最大，不在末尾


def lis_binary(nums: list[int]) -> int:
    """O(n log n) 优化。tails[k] = 长度为 k+1 的递增子序列的最小末尾值。
    复用第 04 章的二分：每个新元素用 bisect 找它该替换的位置。"""
    tails: list[int] = []
    for x in nums:
        pos = bisect_left(tails, x)       # 第一个 >= x 的位置
        if pos == len(tails):
            tails.append(x)               # x 比所有末尾都大 ⇒ 延长
        else:
            tails[pos] = x                # 否则替换，保持各长度末尾最小
    return len(tails)


if __name__ == "__main__":
    a = [10, 9, 2, 5, 3, 7, 101, 18]
    assert lis_dp(a) == 4                 # 例如 2,3,7,18 或 2,5,7,101
    assert lis_binary(a) == 4
    print("ok")

def max_non_overlapping(intervals: list[tuple[int, int]]) -> int:
    """区间 [start, end)。返回最多能选的两两不重叠区间数。O(n log n)。"""
    if not intervals:
        return 0
    intervals.sort(key=lambda iv: iv[1])    # 关键：按结束时间升序
    count = 0
    last_end = float("-inf")                # 已选区间的最晚结束时间
    for start, end in intervals:
        if start >= last_end:               # 与已选不重叠 ⇒ 贪心选中
            count += 1
            last_end = end
    return count


if __name__ == "__main__":
    ivs = [(1, 3), (2, 5), (4, 7), (6, 8), (8, 10)]
    assert max_non_overlapping(ivs) == 3    # (1,3) (4,7) (8,10)
    print("ok")