如何计算带记忆化递归的Word Break单词拆分解法的时间复杂度？

核心前提：记忆化的去重作用 #

你的代码里用了DP数组存储每个下标i的计算结果，每个i（0 ≤ i < n，n是字符串s的长度）只会被计算一次，只要第一次计算完DP[i]被赋值为0或1，后续所有访问都会直接返回结果，不会重复执行递归逻辑，这是避免指数复杂度的核心。

分步计算逻辑 #

• 第一步：确定总状态数
  总共有n个不同的状态（对应i从0到n-1），额外的i=n是边界条件，返回1，开销为O(1)。
• 第二步：计算单个状态的最坏开销
  对于每个未计算的i，你会执行一个从i到s末尾的循环，最多执行n-i次迭代：
  1. 每次迭代拼接1个字符到next字符串，单次拼接操作可以认为是均摊O(1)（C++ string的append操作均摊时间复杂度为O(1)）
  2. 每次调用dict.find(next)查找字符串，unordered_set的平均查找开销是O(k)，k是当前next字符串的长度；最坏情况（哈希全冲突）是O(k*m)，m是字典总大小，这种场景极少见一般不纳入常规复杂度评估。
• 第三步：累加所有状态的总开销
  最坏情况下（比如s是全a字符串，字典包含所有长度的a组合，且没有合法拆分，必须遍历完所有可能性），每个i都要跑完所有n-i次迭代：
  总操作量为 sum_{i=0}^{n-1} sum_{k=1}^{n-i} k = sum_{x=1}^n x(x+1)/2 （x替换为n-i），计算后这个求和的量级是O(n³)。
  如果提前做优化，提前统计字典中单词的最大长度L，循环最多只跑L次，那总复杂度就会降到O(n*L²)，如果L是常量（比如常规自然语言单词最长只有20左右），那复杂度就近似O(n)。
• 补充：平均情况复杂度
  实际场景下如果字典单词长度有限，且存在合法拆分时代码会提前返回，平均复杂度会远低于最坏的O(n³)，大部分业务场景下可以认为是O(n²)量级。

为什么不是指数复杂度？ #

暴力无记忆化的递归实现每次可以选任意长度的前缀拆分，时间复杂度是O(2ⁿ)，但你的实现通过DP缓存了每个位置的结果，每个位置只算一次，所以直接把指数复杂度降到了多项式级别。

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