The only resource available on the internet regarding the application of matrix exponentiation to TWO-DIMENSIONAL dynamic programming problems is this :-
http://threads-iiith.quora.com/Solving-Dynamic-Programming-with-Matrix-Exponentiation
Though the author has covered the topic with nice examples, I have some doubts:-
1) Unlike solving linear recurrences (using matrix exponentiation), I cannot find any solid mathematics behind the steps (or how does it work mathematically) involved in this technique.
2) How are the base-states taken into account in this technique? After building the adjacency-matrix (as is explained in the quora-article), and exponentiating it, what all values do we have to sum up to get the final answer?
I am pretty vague about all these details so any help will be much appreciated.
The key idea is to convert the problem into a graph problem about finding the number of paths in the graph from some source(s) of a fixed length. The process of doing that depends on the problem and I covered some examples in my comment on that thread, you can look into that. Also, the mathematics behind counting number of paths of a fixed length is pretty basic and standard.
Thanks for the reply. Can I assume that the "source(s)" you mention, in fact, represent the base-case? Also, if i'm not mistaken, the matrix should be raised to the power 'n' and not 'n-1' (as is written in the write-up), right?
http://e-maxx.ru/forum/viewtopic.php?id=444
How is this forum post on tree-DP related to solving 2-D DP problems using matrix exponentiation ?
I post some time before, a question about matrix exponentiation maybe this can help you, and i posting a link that i found about this topic. this is the post
Thanks for your post, but the your link is about solving linear recurrences and not 2-D DP problems.
There is one obvious way how to turn some of multi-dimensional recurrences to linear ones. Just like in the last example in your article. For example, if we have 3 parameters (i,j,k) which are bounded: 0<=i<n, 0<=j<m, 0<=k<s, then we can make following substitution: (i,j,k) <-> p=s*(m*i+j)+k, where 0<=p<n*m*s. Now you can re-write all dependences in terms of dp[p]=... But in some cases (hope, not everytime) it can cause more troubles in solving than original problem.
I can't create any really useful example right now, but just to show how it works... Let's take some stupid recurrence: c[i,j]=c[i-1,j]+c[i,j-1] for 1<i<n, 1<j<m. Then we can use the method above: c[i,j]=d[m*i+j] => d[m*i+j]=d[m*i+j-m]+d[m*i+j-1] or simply d[x]=d[x-m]+d[x-1]. And if you have large n but small m — well, maybe it will help.