10069 - Distinct Subsequences

Bueno casi que no hago este problema les cuento la historia.

1. Lo hago en c++. (Wrong Answer)
2. Revizo el algoritmo y corrijo un bug. (Wrong Answer)
3. Caigo en cuenta que el resultado es demasiado grande por lo cual lo intento en Java con BigInteger. (Compile Error).
4. Revizo el porque salio este error y me dice que que la clase no puede declararse publica. Lo envio sin esto (Run Time Error).
5. De la rabia que me dio al no saber porque saco Run Time Error en java. Declare todas las variables en c++ como long long y lo intento de nuevo (Wrong Answer).
6. Despues de tanto desespero me ilumino y me acuerdo que la clase debe de llamarse "Main". Lo cambio y lo envio. (Time Limit Exceeded).

Por mi salud mental dejo este problema así.

Dia siguiente.

7. Me propongo a mejorar el algoritmo para que corra más rapido en la lenteja de Java. (Time Limit Exceeded).
8. Me quedo un rato pensando en como optimizarlo al maximo y le hago más mejoras al algoritmo (Wrong Answer).
9. Bueno me dio felicidad al saber que almenos ejecuto en java pero fallo. Caigo en cuenta del caso trivial y lo mando (Accepted).

Bueno el que persevera alcanza y este ejercicio me enseño bastante de como mandar problemas en Java y mucha experiencia, jeje.

Ahora si como lo resolvi.

dp[i][j] = Número de veces en que la subcadena Z0...Zi está en la subcadena X0...Xj.