单词拆分问题的自顶向下动态规划代码的时间复杂度是多少？

先明确变量定义：

• n 为输入字符串 s 的长度
• k 为字典 wordDict 的大小
• L 为字典中单词的平均长度，W 为字典中单词的最大长度

核心逻辑说明 #

你贴的代码是带备忘录的自顶向下动态规划实现：

• 用参数 l 表示当前需要匹配的子串在 s 中的起始下标，备忘录 m 存储每个下标 l 开始的子串是否可以被合法拆分的结果，避免重复计算
• 对于每个 l，遍历字典中所有单词，调用 match 函数判断该单词是否和 s 从 l 开始的前缀匹配，匹配成功则递归判断 l + 单词长度 位置开始的子串是否可以拆分
• 只要找到一条合法拆分路径就返回 true，所有单词遍历完都没有合法路径则将 m[l] 设为 false 并返回

时间复杂度计算 #

1. 总状态数：l 的取值范围是 0 到 n，最多有 n+1 个不同的状态，每个状态只会被计算一次，计算后就存入备忘录，后续直接读取无需重复计算
2. 单状态开销：每个状态需要遍历字典的 k 个单词，每个单词的 match 匹配操作时间复杂度等于单词长度，平均为 O(L)，最坏为 O(W)，因此每个状态的处理开销为 O(k*L)
3. 额外开销：代码中使用 std::map 实现备忘录，单次查找的时间复杂度为 O(logn)，这部分开销远低于主逻辑开销，可以忽略；如果替换为 unordered_map 查找开销为 O(1)，也不影响主时间复杂度

综上，这段代码的时间复杂度为 O(n * k * L)，如果按字典单词最大长度计算则为 O(n * k * W)。

内容的提问来源于stack exchange，提问作者Ranju