根据线性递推的DP公式如何写出变换矩阵

原理

一组DP状态&＃xff0c;其实等价于一个向量。而DP状态的转移方程&＃xff0c;可以是对一个向量做变形的矩阵。那么本质上从1个向量到另一个状态的向量&＃xff0c;是可以通过一个矩阵来做到。矩阵具有结合律&＃xff0c;我们可以先对右半部分矩阵用快速幂得到一个终极的变形矩阵&＃xff0c;再乘以向量&＃xff0c;就可以把$O(N)$的计算 优化到 $O(log(N))$

示例

以大家最熟悉的斐波那契数列为例&＃xff1a;

递推公式为 $dp[i]\&＃61;dp[i-1]\&＃43;dp[i-2]$&＃xff0c;那么每一个新的数的计算依赖于前2个数&＃xff0c;所以可以构建这么一个向量为 $(dp[n-1],dp[n-2])$&＃xff0c;那么它和递推的下一组$(dp[n],dp[n-1])$有什么关系呢&＃xff1f;

• $dp[n]\&＃61;dp[n-1]\ast 1\&＃43;dp[n-2]\ast 1$
• $dp[n-1]\&＃61;dp[n-1]\ast 1\&＃61;dp[n-1]\ast 1\&＃43;dp[n-2]\ast 0$

转换为矩阵形式&＃xff0c;显而易见&＃xff1a;
依次递推&＃xff0c;要从 $dp[2],dp[1]$求到 $dp[n],dp[n-1]$ 中间需要有n-2个同样的变形矩阵的乘法

&＃xff08;此处若n比较大&＃xff0c;则需要结合矩阵快速幂优化&＃xff09;

 传送门&＃xff1a;矩阵快速幂优化

注&＃xff1a;
本文部分引自西部小笼包https://www.jianshu.com/p/9817cf3c2fd9