algorithm - 大尺寸二维 DP

Question

给定一个 n+1 元组（a ₀ , a ₁ , ..., a _n）。

我们需要计算 F(m, n)。

鉴于：

一个₀ <= 一个₁ <= ... <= 一个_n

F(x, y) = a _y * F(x - 1, y) + F(x, y - 1)

F(0, y) = 1 对于所有 y

F(x, 0) = 一个₀ ^x

我在考虑 dp 方法，但我面临的问题是“m”太大，可能大于十亿。

有没有办法解决这个问题？

我觉得这可以转换为矩阵求幂问题，但无法弄清楚如何？

我也是堆栈溢出和编程的新手。任何有问题的编辑建议和问题的方法/解决方案将不胜感激。

标签： algorithmmathmatrixdynamic-programming

Answer 1

您的“矩阵求幂”想法是正确的。

写F(x, _)为垂直向量。（也就是说，每个 的值对应一个条目y。）

有A这样一个矩阵F(x+1, _) = A * F(x, _)。一经发现，原来如此F(x+k, _) = A^k * F(x, _)。

现在你知道了F(0, _)。你可以找到A. 然后通过重复平方你可以找到A^m，现在你可以回答你的问题。