Icebound

最近莫名其妙的做了许多矩阵优化DP的题。。。在这里做一下总结。。。
矩阵优化dp，是将dp的状态化为矩阵，dp的转移也化为矩阵，将转移变为矩阵乘法的过程。
1.什么样的题可以用矩阵优化？
目前发现两类：
第一类：
线性常系数递推方程，就是像斐波那契数列那样的（f[i]=f[i-1]+f[i-2])
对于这样的题，我们需要构造2个矩阵，初始矩阵，转移矩阵。
初始矩阵我们一般认为是列向量，转移矩阵一般为一个N*N的方阵。
READ MORE →