如何解决涉及两个函数的线性递归问题？

Question

实际上，我在动态规划中遇到了一个问题，我们需要找到用给定尺寸的瓷砖平铺2XN区域的方法。以下是问题陈述

经过一些反复的解决，我拿出了这些。

F(n) = F(n-1) + F(n-2) + 2G(n-1)，以及

G(n) = G(n-1) + F(n-1)

我知道如何求解一个函数为there.For大N的LR模型，就像上面问题中的情况一样，我们可以进行矩阵指数运算，实现O(k^3log(N))时间，其中k是最小数，使得对于所有k>m F(n)都不依赖于F( not )。在那个博客中给出了用矩阵指数法求解线性递推的方法。

现在，对于涉及两个函数的LR，任何人都可以建议一种足够适合大N的方法吗？

Answer 1

同样的方法有效:找到一个将(F(n-1) F(n-2) G(n-1))转换为(F(n) F(n-1) G(n))的矩阵。((1 1 2) (1 0 0) (1 0 1))矩阵就能做到这一点。

解释

这就是矩阵对向量乘法的工作原理。生成向量的第一个元素是第一行和初始向量的内积：

1*F(n-1) + 1*F(n-2) + 2*G(n-1)

根据复发的结果是F(n)。第二和第三也是一样的。