c++ - 寻找递归关系和矩阵求幂

Question

我试图在 Codechef 上找到这个问题的递归关系:

http://www.codechef.com/problems/BWALL

我知道一旦找到它，我就可以使用矩阵求幂轻松求解。但我无法理解它是如何得到正确答案的。这里有一个解决方案，但我希望有人能以更好的方式解释它？

是否有简单的经验法则来查找重复或类似的东西？谢谢!

Answer 1

找到重现的“一般规则”是了解问题的解决方案与较小问题的解决方案之间的关系。但不仅如此，我认为没有找到复发的通用程序。

对于这个特定示例，您可以通过以下方式找到重复项。

假设你有一堵 N 大的墙。现在，看看墙的尽头。更准确地说，从墙的尽头，找到第一个有“垂直分隔”的地方，即第一个可以将墙分成两个没有 L 形的较小墙的地方。

示例:

(A) 这是墙:

X###X#XXX#X

XX#XX#XXXXX

与结尾的 split 给你:

X###X#XXX #X

XX#XX#XXX XX

(B) 另一面墙

X###X#XXX

XX#XX#XXX

与结尾的 split 给你:

X###X# XXX

XX#XX# XXX

在 split 和墙的末端之间你能得到的小块墙的尺寸是多少？好吧，您可以有 1、2 或 3，但不能更多(否则，您可以进行最小的拆分)。

小块的可能性其实就是你问题中给出的(是的，7个小块)。

因此，要 build 一堵大小为 N 的墙，您必须:

• build 一堵大小为 N-1 的墙并添加到大小为 1 的小方 block 的尽头
• 或者 build 一堵大小为 N-2 的墙并添加到四个大小为 2 的 block 之一的末端
• 或 build 一堵 N-3 尺寸的墙，并添加到两个 3 尺寸 block 之一的末端。

因此，大小为 N 的可能墙的数量 T(N) 是

• 大小为 N-1 的墙的数量(最后是大小为 1 的方 block )-> T(N-1)
• 加上尺寸为 N-2 的墙的数量以及 4 个可能的端 block (尺寸为 2)-> 4 T(N-2)
• 加上尺寸为 N-3 的墙的数量，带有 2 个可能的端 block (尺寸为 3)-> 2 T(N-3)

然后你就得到了你的复发。

希望对您有所帮助!