问题描述:

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).