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

9 Years
Discussion Span
Last Post by thoughtcoder

I am sorry I wrote that in a hurry, so it is hard to understand
Here is an example of input:

2 3 // n m
10 90 //matrix of posibilities nxn
90 10
aa //matrix of chars nxn
aab //final sequence of chars with length m
And my task is to find most probable way how was the final sequence created.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.