TANGLED: DP Method

general
, ,
1

Is it possible to solve http://www.codechef.com/problems/TANGLED/ through DP ?

Example:

Input:

abab

babc

4

    b a b c 
    | | | |    
a - 0 0 0 0 0

b - 0 0 1 0 0

a - 0 1 0 2 0

b - 0 0 2 0 0

    0 1 0 3 0

Now we can easily get the answer by traversing through the 2d array !

For L=1 We count all the elements greater than or equal to 1.

For L=2 We count all the elements greater than or equal to 2.

For L=3 We count all the elements greater than or equal to 3.
.

.

.

.

.

And So On.