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
Lazzi
0
Newbie Poster
Recommended Answers
Jump to PostFirst you say you have a sequence of chars, but then you say you have a matrix of chars. Which is it?
Jump to PostWait, I misread you -- how is an nxn matrix of chars an input?
All 5 Replies
thoughtcoder
167
Junior Poster
thoughtcoder
167
Junior Poster
Lazzi
0
Newbie Poster
thoughtcoder
167
Junior Poster
thoughtcoder
167
Junior Poster
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.