DP 经典模型进阶

dp[i][w]:
     w=0  w=1  w=2  w=3  w=4  w=5
i=0 |  0    0    0    0    0    0
i=1 |  0    0    3    3    3    3
i=2 |  0    0    3    4    4    7
i=3 |  0    0    3    4    5    7

def knapsack_01(weights: list[int], values: list[int], capacity: int) -> int:
    """0-1 背包二维实现。时间 O(nW)，空间 O(nW)。"""
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]
            if w >= weights[i - 1]:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
    return dp[n][capacity]

def knapsack_01_optimized(weights: list[int], values: list[int], capacity: int) -> int:
    """0-1 背包一维实现。空间 O(W)。"""
    n = len(weights)
    dp = [0] * (capacity + 1)
    for i in range(n):
        # 关键：w 递减，保证 dp[w - weights[i]] 仍是上一阶段值
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

# 测试
print(knapsack_01([2, 3, 4], [3, 4, 5], 5))           # 输出: 7
print(knapsack_01_optimized([2, 3, 4], [3, 4, 5], 5)) # 输出: 7

#include <algorithm>
#include <vector>

// 0-1 背包二维实现。
int knapsack01(const std::vector<int>& weights,
               const std::vector<int>& values,
               int capacity) {
    int n = weights.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(capacity + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            dp[i][w] = dp[i - 1][w];
            if (w >= weights[i - 1]) {
                dp[i][w] = std::max(dp[i][w],
                                    dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    return dp[n][capacity];
}

// 0-1 背包一维优化。
int knapsack01Optimized(const std::vector<int>& weights,
                        const std::vector<int>& values,
                        int capacity) {
    int n = weights.size();
    std::vector<int> dp(capacity + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int w = capacity; w >= weights[i]; w--) {
            dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

def knapsack_complete(weights: list[int], values: list[int], capacity: int) -> int:
    """完全背包。内层 w 递增。"""
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for w in range(weights[i], capacity + 1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

# 测试
print(knapsack_complete([2, 3, 4], [3, 4, 5], 5))  # 输出: 7

int knapsackComplete(const std::vector<int>& weights,
                     const std::vector<int>& values,
                     int capacity) {
    int n = weights.size();
    std::vector<int> dp(capacity + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int w = weights[i]; w <= capacity; w++) {
            dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

def knapsack_multiple(weights: list[int], values: list[int],
                      counts: list[int], capacity: int) -> int:
    """多重背包二进制拆分优化。"""
    items = []
    for i in range(len(weights)):
        cnt, k = counts[i], 1
        while cnt > 0:
            take = min(k, cnt)
            items.append((weights[i] * take, values[i] * take))
            cnt -= take
            k *= 2
    dp = [0] * (capacity + 1)
    for w, v in items:
        for j in range(capacity, w - 1, -1):
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[capacity]

# 测试
print(knapsack_multiple([2, 3, 4], [3, 4, 5], [2, 3, 1], 10))  # 输出: 14

int knapsackMultiple(std::vector<int>& weights,
                     std::vector<int>& values,
                     std::vector<int>& counts,
                     int capacity) {
    std::vector<std::pair<int, int>> items;
    for (int i = 0; i < (int)weights.size(); i++) {
        int cnt = counts[i], k = 1;
        while (cnt > 0) {
            int take = std::min(k, cnt);
            items.push_back({weights[i] * take, values[i] * take});
            cnt -= take;
            k *= 2;
        }
    }
    std::vector<int> dp(capacity + 1, 0);
    for (auto& [w, v] : items) {
        for (int j = capacity; j >= w; j--) {
            dp[j] = std::max(dp[j], dp[j - w] + v);
        }
    }
    return dp[capacity];
}

def knapsack_grouped(groups: list[list[tuple[int, int]]], capacity: int) -> int:
    """分组背包。groups[i] 是第 i 组的 (w, v) 列表。"""
    dp = [0] * (capacity + 1)
    for group in groups:
        # 每组内只能选 1 个，w 递减避免同组多次选取
        for w in range(capacity, -1, -1):
            for gw, gv in group:
                if w >= gw:
                    dp[w] = max(dp[w], dp[w - gw] + gv)
    return dp[capacity]

# 测试
groups = [[(2, 3), (3, 4)], [(4, 5), (5, 6)]]
print(knapsack_grouped(groups, 7))  # 输出: 9

def matrix_chain_order(p: list[int]) -> int:
    """矩阵链乘法最少乘法次数。时间 O(n^3)，空间 O(n^2)。"""
    n = len(p) - 1
    if n <= 0:
        return 0
    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] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n - 1]

# 测试：3 个矩阵 10x100, 100x5, 5x50，最优为 7500
print(matrix_chain_order([10, 100, 5, 50]))  # 输出: 7500

#include <climits>
#include <vector>

// 矩阵链乘法最少乘法次数。
int matrixChainOrder(const std::vector<int>& p) {
    int n = (int)p.size() - 1;
    if (n <= 0) return 0;
    std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
    for (int length = 2; length <= n; length++) {
        for (int i = 0; i <= n - length; i++) {
            int j = i + length - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k + 1][j] +
                           p[i] * p[k + 1] * p[j + 1];
                if (cost < dp[i][j]) dp[i][j] = cost;
            }
        }
    }
    return dp[0][n - 1];
}

def max_coins(nums: list[int]) -> int:
    """戳气球。时间 O(n^3)，空间 O(n^2)。"""
    # 添加虚拟边界
    vals = [1] + nums + [1]
    n = len(vals)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for i in range(n - length):
            j = i + length
            for k in range(i + 1, j):
                dp[i][j] = max(dp[i][j],
                               dp[i][k] + dp[k][j] +
                               vals[i] * vals[k] * vals[j])
    return dp[0][n - 1]

# 测试
print(max_coins([3, 1, 5, 8]))  # 输出: 167

def merge_stones(stones: list[int]) -> int:
    """合并石子最小代价。时间 O(n^3)，空间 O(n^2)。"""
    n = len(stones)
    if n == 0:
        return 0
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + stones[i]
    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] = float('inf')
            for k in range(i, j):
                dp[i][j] = min(dp[i][j],
                               dp[i][k] + dp[k + 1][j])
            dp[i][j] += prefix[j + 1] - prefix[i]
    return dp[0][n - 1]

# 测试
print(merge_stones([3, 1, 4, 1, 5]))  # 输出: 32

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rob_tree(root: Optional[TreeNode]) -> int:
    """打家劫舍 III。后序遍历。"""
    def dfs(node: Optional[TreeNode]) -> tuple[int, int]:
        if not node:
            return (0, 0)
        left = dfs(node.left)
        right = dfs(node.right)
        # (不偷当前, 偷当前)
        not_rob = max(left) + max(right)
        rob = node.val + left[0] + right[0]
        return (not_rob, rob)
    return max(dfs(root))

# 测试：树 [3,2,3,null,3,null,1]
root = TreeNode(3,
                TreeNode(2, None, TreeNode(3)),
                TreeNode(3, None, TreeNode(1)))
print(rob_tree(root))  # 输出: 7

def max_path_sum(root: Optional[TreeNode]) -> int:
    """二叉树最大路径和。"""
    result = [float('-inf')]

    def dfs(node: Optional[TreeNode]) -> int:
        if not node:
            return 0
        left = max(dfs(node.left), 0)
        right = max(dfs(node.right), 0)
        # 经过当前节点的路径和
        result[0] = max(result[0], node.val + left + right)
        # 只能选一侧向上返回
        return node.val + max(left, right)

    dfs(root)
    return int(result[0])

# 测试：树 [-10,9,20,null,null,15,7]
root = TreeNode(-10,
                TreeNode(9),
                TreeNode(20, TreeNode(15), TreeNode(7)))
print(max_path_sum(root))  # 输出: 42

def diameter_of_binary_tree(root: Optional[TreeNode]) -> int:
    """二叉树直径。"""
    result = [0]

    def dfs(node: Optional[TreeNode]) -> int:
        if not node:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        result[0] = max(result[0], left + right)
        return 1 + max(left, right)

    dfs(root)
    return result[0]

def party_no_boss(n: int, happy: list[int], edges: list[tuple[int, int]]) -> int:
    """没有上司的舞会。"""
    from collections import defaultdict
    graph = defaultdict(list)
    has_parent = [False] * n
    for u, v in edges:
        graph[u].append(v)
        has_parent[v] = True
    root = next(i for i in range(n) if not has_parent[i])

    def dfs(u: int) -> tuple[int, int]:
        attend, not_attend = happy[u], 0
        for v in graph[u]:
            a, na = dfs(v)
            attend += na  # 上司出席则下属不出席
            not_attend += max(a, na)
        return (attend, not_attend)

    return max(dfs(root))

# 测试：5 个节点
print(party_no_boss(5, [3, 2, 1, 10, 4],
                    [(0, 1), (0, 2), (1, 3), (1, 4)]))  # 输出: 17

# 添加元素 i
S | (1 << i)
# 删除元素 i
S & ~(1 << i)
# 检查元素 i 是否在集合中
(S >> i) & 1
# 集合大小（1 的个数）
bin(S).count('1')
# 枚举 S 的所有非空子集
sub = S
while sub > 0:
    # 处理 sub
    sub = (sub - 1) & S

def tsp(dist: list[list[int]]) -> int:
    """旅行商问题。时间 O(2^n * n^2)，空间 O(2^n * n)。"""
    n = len(dist)
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # 起点：只访问城市 0
    for mask in range(1, 1 << n):
        for u in range(n):
            if not (mask & (1 << u)):
                continue
            for v in range(n):
                if mask & (1 << v):
                    continue
                new_mask = mask | (1 << v)
                dp[new_mask][v] = min(dp[new_mask][v],
                                      dp[mask][u] + dist[u][v])
    full_mask = (1 << n) - 1
    return min(dp[full_mask][u] + dist[u][0] for u in range(1, n))

# 测试：4 个城市
dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
]
print(tsp(dist))  # 输出: 80

#include <climits>
#include <vector>

// TSP 状压 DP。
int tsp(const std::vector<std::vector<int>>& dist) {
    int n = (int)dist.size();
    int fullMask = (1 << n) - 1;
    std::vector<std::vector<int>> dp(1 << n, std::vector<int>(n, INT_MAX / 2));
    dp[1][0] = 0;
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u))) continue;
            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;
                int newMask = mask | (1 << v);
                dp[newMask][v] = std::min(dp[newMask][v],
                                          dp[mask][u] + dist[u][v]);
            }
        }
    }
    int result = INT_MAX;
    for (int u = 1; u < n; u++) {
        result = std::min(result, dp[fullMask][u] + dist[u][0]);
    }
    return result;
}

def sum_over_subsets(arr: list[int]) -> list[int]:
    """Sum Over Subsets (SOS) DP。时间 O(n * 2^n)。"""
    n = len(arr).bit_length() - 1
    dp = arr[:]
    for i in range(n):
        for mask in range(1 << n):
            if mask & (1 << i):
                dp[mask] += dp[mask ^ (1 << i)]
    return dp

# 测试
print(sum_over_subsets([1, 2, 4, 8]))  # 输出: [1, 3, 5, 15]

def find_integers(n: int) -> int:
    """不含连续 1 的整数个数。数位 DP。"""
    s = bin(n)[2:]
    length = len(s)

    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dfs(pos: int, prev: int, tight: bool) -> int:
        if pos == length:
            return 1
        limit = int(s[pos]) if tight else 1
        total = 0
        for d in range(0, limit + 1):
            new_tight = tight and (d == limit)
            if d == 1 and prev == 1:
                continue  # 不能连续 1
            total += dfs(pos + 1, d, new_tight)
        return total

    return dfs(0, 0, True)

# 测试
print(find_integers(5))   # 输出: 5  (0, 1, 10, 100, 101)
print(find_integers(10))  # 输出: 8

def count_digit_one(n: int) -> int:
    """数位 1 出现总次数。"""
    s = str(n)
    length = len(s)

    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dfs(pos: int, cnt: int, tight: bool) -> int:
        if pos == length:
            return cnt
        limit = int(s[pos]) if tight else 9
        total = 0
        for d in range(0, limit + 1):
            new_tight = tight and (d == limit)
            total += dfs(pos + 1, cnt + (1 if d == 1 else 0), new_tight)
        return total

    return dfs(0, 0, True)

# 测试
print(count_digit_one(13))  # 输出: 6

def count_with_digit_sum(n: int, k: int) -> int:
    """各位数字之和不超过 k 的数。"""
    s = str(n)
    length = len(s)

    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dfs(pos: int, sum_so_far: int, tight: bool) -> int:
        if sum_so_far > k:
            return 0
        if pos == length:
            return 1
        limit = int(s[pos]) if tight else 9
        total = 0
        for d in range(0, limit + 1):
            new_tight = tight and (d == limit)
            total += dfs(pos + 1, sum_so_far + d, new_tight)
        return total

    return dfs(0, 0, True) - 1  # 减去 0

# 测试
print(count_with_digit_sum(20, 5))  # 输出: 11

# 二维 LCS 压缩为两行
def lcs_rolling(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    prev = [0] * (n + 1)
    for i in range(1, m + 1):
        curr = [0] * (n + 1)
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev = curr
    return prev[n]

print(lcs_rolling("abcde", "ace"))  # 输出: 3

from collections import deque

def sliding_window_max(nums: list[int], k: int) -> list[int]:
    """滑动窗口最大值。时间 O(n)，空间 O(k)。"""
    dq = deque()
    result = []
    for i, x in enumerate(nums):
        # 维护单调递减队列
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        # 移除超出窗口的元素
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

# 测试
print(sliding_window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
# 输出: [3, 3, 5, 5, 6, 7]

from collections import deque

def slope_dp(n: int) -> int:
    """斜率优化 DP 示例：dp[i] = min_{j<i} (dp[j] + (i-j)^2)。"""
    dp = [0] * (n + 1)
    dq = deque([0])  # 决策点队列
    for i in range(1, n + 1):
        # 队首弹出非最优决策
        while len(dq) >= 2:
            j1, j2 = dq[0], dq[1]
            if dp[j1] + (i - j1) ** 2 >= dp[j2] + (i - j2) ** 2:
                dq.popleft()
            else:
                break
        j = dq[0]
        dp[i] = dp[j] + (i - j) ** 2
        # 维护下凸包：弹出不满足凸性的队尾
        while len(dq) >= 2:
            j1, j2 = dq[-2], dq[-1]
            # 斜率比较：(dp[j2]-dp[j1])/(j2-j1) >= (dp[i]-dp[j2])/(i-j2)
            # 化为整数乘法避免浮点
            if (dp[j2] - dp[j1]) * (i - j2) >= (dp[i] - dp[j2]) * (j2 - j1):
                dq.pop()
            else:
                break
        dq.append(i)
    return dp[n]

# 测试
print(slope_dp(10))  # 输出: 10 (i^2 当 j=0 时最小)

# 0-1 背包遗漏 w >= w_i 判断
for i in range(1, n + 1):
    for w in range(capacity + 1):
        # 未判断 w >= weights[i-1]，导致越界
        dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])

# 0-1 背包一维数组 w 递增遍历（退化为完全背包）
for i in range(n):
    for w in range(weights[i], capacity + 1):  # 错误：递增
        dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

# 最长回文子序列错误按 i 递减、j 递增双循环
for i in range(n - 1, -1, -1):
    for j in range(i + 1, n):
        # length=2 时 dp[i+1][j-1] = dp[j][i] 为 0（恰好正确）
        # 但 length=3 时 dp[i+1][j-1] = dp[i+1][i+1] 应为 1
        # 而双循环顺序可能尚未计算
        ...

# 多重背包未做二进制拆分，直接展开导致 TLE
for i in range(n):
    for _ in range(counts[i]):
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
# 当 counts[i] 很大时复杂度爆炸

# n=30 时直接枚举 2^30 ≈ 10^9 个状态 —— 内存与时间均爆炸
dp = [[0] * 30 for _ in range(1 << 30)]

# 0-1 背包问题在 W=10^9 时直接套用 O(nW) —— TLE
# 该复杂度是伪多项式，严格意义下为指数级

def smith_waterman(seq1: str, seq2: str,
                   match: int = 2, mismatch: int = -1, gap: int = -1) -> int:
    """Smith-Waterman 局部序列比对。

    输入参数:
        seq1, seq2: 待比对的两条序列（DNA/蛋白质/字符串）
        match: 相同字符的得分
        mismatch: 不同字符的罚分
        gap: 空位罚分

    返回值:
        最优局部比对的最大得分

    核心流程:
        1. 构造 (m+1) × (n+1) 的得分矩阵 dp
        2. 对每个单元按 Bellman 方程递推
        3. 跟踪全局最大值（局部比对的关键：允许从 0 重启）
    """
    m, n = len(seq1), len(seq2)
    # dp[i][j] 表示以 seq1[i-1] 与 seq2[j-1] 结尾的最优局部比对得分
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_score = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            score = match if seq1[i - 1] == seq2[j - 1] else mismatch
            # 局部比对核心：取 0 表示在此处重新开始比对
            dp[i][j] = max(0,
                           dp[i - 1][j - 1] + score,
                           dp[i - 1][j] + gap,
                           dp[i][j - 1] + gap)
            max_score = max(max_score, dp[i][j])
    return max_score

# 预期输出: 13
# 示例: seq1="ACGTACGT", seq2="AGTACGT"
# 局部最优对齐:
#   ACGTACGT
#   A-GTACGT  (一个 gap：7 个 match * 2 - 1 个 gap * 1 = 14 - 1 = 13)
print(smith_waterman("ACGTACGT", "AGTACGT"))

#include <algorithm>
#include <string>
#include <vector>

// Smith-Waterman 局部序列比对（C++ 实现）
int smithWaterman(const std::string& seq1, const std::string& seq2,
                  int match = 2, int mismatch = -1, int gap = -1) {
    const int m = seq1.size();
    const int n = seq2.size();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
    int maxScore = 0;
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            int score = (seq1[i - 1] == seq2[j - 1]) ? match : mismatch;
            dp[i][j] = std::max({0,
                                 dp[i - 1][j - 1] + score,
                                 dp[i - 1][j] + gap,
                                 dp[i][j - 1] + gap});
            maxScore = std::max(maxScore, dp[i][j]);
        }
    }
    return maxScore;
}
// 预期输出: 13（与 Python 实现一致，参数 match=2, gap=-1）

public final class SmithWaterman {
    private SmithWaterman() {}

    /** Smith-Waterman 局部序列比对（Java 实现）。 */
    public static int align(String seq1, String seq2,
                            int match, int mismatch, int gap) {
        int m = seq1.length();
        int n = seq2.length();
        int[][] dp = new int[m + 1][n + 1];
        int maxScore = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int score = seq1.charAt(i - 1) == seq2.charAt(j - 1) ? match : mismatch;
                dp[i][j] = Math.max(0,
                          Math.max(dp[i - 1][j - 1] + score,
                          Math.max(dp[i - 1][j] + gap,
                                   dp[i][j - 1] + gap)));
                maxScore = Math.max(maxScore, dp[i][j]);
            }
        }
        return maxScore;
    }
}
// 预期输出: 13

from typing import Sequence

def viterbi(observations: Sequence[str],
            states: Sequence[str],
            start_p: dict[str, float],
            trans_p: dict[str, dict[str, float]],
            emit_p: dict[str, dict[str, float]]) -> list[str]:
    """Viterbi 算法求 HMM 最优状态路径。

    输入参数:
        observations: 观测序列（如分词后的字符序列）
        states: 所有可能的隐状态集合
        start_p: 初始状态概率
        trans_p: 状态转移概率
        emit_p: 发射概率

    返回值:
        最优状态序列
    """
    # V[t][s] = 时刻 t 处于状态 s 的最大概率
    V = [{}]
    # path[s] = 到达状态 s 的最优路径
    path = {}

    # 初始化（t = 0）
    for s in states:
        V[0][s] = start_p.get(s, 0.0) * emit_p.get(s, {}).get(observations[0], 0.0)
        path[s] = [s]

    # 递推（t > 0）
    for t in range(1, len(observations)):
        V.append({})
        new_path = {}
        for curr in states:
            # 在所有前驱状态中选择使概率最大的
            best_prev, best_prob = max(
                ((prev, V[t - 1][prev] * trans_p.get(prev, {}).get(curr, 0.0))
                 for prev in states),
                key=lambda x: x[1]
            )
            V[t][curr] = best_prob * emit_p.get(curr, {}).get(observations[t], 0.0)
            new_path[curr] = path[best_prev] + [curr]
        path = new_path

    # 终止：选择最后一个时刻概率最大的状态
    best_final = max(states, key=lambda s: V[-1].get(s, 0.0))
    return path[best_final]

# 预期输出: ['SUNNY', 'SUNNY', 'RAINY']
# 示例: 海藻湿度观测序列 ['dry', 'damp', 'soggy']，根据 HMM 推断最可能的天气

def american_option_price(S0: float, K: float, r: float, sigma: float,
                          T: float, steps: int, is_call: bool = True) -> float:
    """Cox-Ross-Rubinstein 二叉树模型为美式期权定价。

    输入参数:
        S0: 标的资产现价
        K: 行权价
        r: 无风险利率（年化）
        sigma: 波动率（年化）
        T: 到期时间（年）
        steps: 二叉树步数
        is_call: True 为看涨期权，False 为看跌期权

    返回值:
        美式期权现价
    """
    import math
    dt = T / steps
    u = math.exp(sigma * math.sqrt(dt))      # 上涨因子
    d = 1 / u                                 # 下跌因子
    p = (math.exp(r * dt) - d) / (u - d)     # 风险中性概率
    discount = math.exp(-r * dt)

    # 内在价值函数
    def payoff(price: float) -> float:
        return max(price - K, 0.0) if is_call else max(K - price, 0.0)

    # 叶子节点（到期时刻）的期权价值
    prices = [S0 * (u ** (steps - i)) * (d ** i) for i in range(steps + 1)]
    values = [payoff(p) for p in prices]

    # 后向归纳
    for n in range(steps - 1, -1, -1):
        for i in range(n + 1):
            price = S0 * (u ** (n - i)) * (d ** i)
            hold = discount * (p * values[i] + (1 - p) * values[i + 1])
            # 美式期权关键：随时可提前行权
            values[i] = max(payoff(price), hold)
        # 最后一层需要截断到 n+1 个元素
        values = values[:n + 1]

    return values[0]

# 预期输出: 约 10.45（参数 S0=100, K=100, r=0.05, sigma=0.2, T=1, steps=100, is_call=True）

def detect_arbitrage(rates: dict[str, dict[str, float]]) -> bool:
    """检测汇率市场是否存在套利机会（负环）。

    输入参数:
        rates: 嵌套字典，rates[u][v] 表示 1 单位 u 兑换多少 v

    返回值:
        True 表示存在套利机会
    """
    currencies = list(rates.keys())
    # 取对数将乘法转化为加法，套利条件 "乘积 > 1" 变为 "和 < 0"
    dist = {c: 0.0 for c in currencies}  # 从虚拟源点出发，初始全 0

    n = len(currencies)
    for k in range(n):
        updated = False
        for u in currencies:
            for v in currencies:
                if u == v or v not in rates.get(u, {}):
                    continue
                w = -__import__('math').log(rates[u][v])
                if dist[u] + w < dist[v] - 1e-12:
                    dist[v] = dist[u] + w
                    updated = True
        # 第 n 轮仍能松弛，则存在负环
        if k == n - 1:
            return updated
        if not updated:
            return False
    return False

# 预期输出: True
# 示例: rates = {'USD': {'EUR': 0.9}, 'EUR': {'CNY': 8}, 'CNY': {'USD': 0.15}}
# USD -> EUR -> CNY -> USD = 0.9 * 8 * 0.15 = 1.08 > 1，存在套利