Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
是否可以在计算字符串的幂集(即该字符串的所有可能子序列)时使用动态规划来显着减少计算次数?
不。如果您正在计算一个幂集,那么您正在计算一个幂集,它始终具有相同数量的元素。
您永远无法将复杂性降低到与输出大小成线性关系以下,因为您需要以某种方式遍历每个输出位。无论使用何种算法,所有问题都是如此。所以 2^n 是计算幂集的下限,因为你需要输出 2^n 个字符串(每个字符串都是多个字符,平均取决于 n,所以甚至更高)。