Hi I have to solve this problem with dynamic programming

We have system that generates sequence of chars, system can be only in one stat at a time. If system is in the state qi in the next step he goes to state qj with probability pij while generating char aij.

As input we have:

number n

matrix p(matrix of probabilities), its size is nxn

matrix a(matrix of chars), also nxn

sequence of chars

I need to find most probable way, how was the sequence of chars in the input created. I just need some hints, how to solve it effectivelly with dynamic programming(I found one solution but I think it is too time and computational complex), if I could use tree, it would be easy, but I cant.

Thanks for all advices

0