问题描述:

Is it possible to use dynamic programming in the calculation of power set of a string (ie, all possible subsequences of that string) to reduce the number of computations significantly?

网友答案:

No. If you are calculating a powerset, you are calculating a powerset, which always has the same number of elements.

网友答案:

You can never reduce complexity below linear with the size of the output, because you need go through each of the output bits some way or another. This is true for all problems, regardless of algorithm used. So 2^n is the lower bound for computation of the power set, because you need to output 2^n strings (and every string is multiple characters, which depends on n on average, so even higher).

相关阅读:
Top