can anyone please explain , what will be recurrence relation of MBLAST problem from SPOJ. I’m unable to get it.

PS: I implemented this recursion+memoization approach which got accepted but still I’m not able to figure out how to implement it in top-down / bottom-up manner.

DP[i][j] = min (

DP[i-1][j]+K,

DP[i][j-1]+K,

DP[i][j]= DP[i-1][j-1]+abs(A[i]-B[j])

)

Where 1 \leq i <|A| and 1 \leq j <|B|

Where A and B are original strings in input and |A| denotes length of string A.

I think this is Bottom up iterative DP

2 Likes

thank you very much for your response , but i’m struggling at understanding it in a intuitive way ( why it works ) .

At last I found this link very useful (atleast for me).

If you want to add something more , please do so.

Generally when you want to convert a recurrence to iterative version.

If dp[i][j] in your recurrence depends on dp[x][y] then add a directed edge from (x,y) to (i,j)

This graph will be called “graph of dependency”.

Now you need to compute “topological sort” on it. Google search topological sort if you are not aware about it. Just understand what is topological sort. You don’t need to understand how to do topological sort.

So take two small strings. Make a "graph of dependency " and find in which order should you iterate the values so that it follows topological ordering. Observe the pattern and generalize it.

This is how a general recurrence is converted to iterative DP.

4 Likes