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

Question

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

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

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

是否有一个简单的经验法则可以找到复发或类似的东西？谢谢！

Answer 1

找到递归的“一般规则”是了解问题的解决方案与较小问题的解决方案之间的关系。但更重要的是，我认为没有找到复发的一般程序。

对于这个特定的例子，这里是你如何找到重复的方法。

假设你有一堵大小为 N 的大墙。现在，看看墙的末端。更准确地说，从墙的末端开始，找到第一个具有“垂直分隔”的位置，即第一个可以将墙分成两个没有 L 形的较小墙的位置。

例子：

(A) 这是墙：

X###X#XXX#X

XX#XX#XXXXX

与结束的分裂给你：

X###X#XXX #X

XX#XX#XXX XX

(B) 另一面墙

X###X#XXX

XX#XX#XXX

与结束的分裂给你：

X###X#XXX

XX#XX#XXX

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

小块的可能性实际上是您问题中给出的可能性（是的，7 个小块）。

因此，要建造尺寸为 N 的墙，您必须：

• 建造一堵大小为 N-1 的墙并添加到大小为 1 的小块的末端
• 或建造一堵大小为 N-2 的墙并添加到四个大小为 2 的块之一的末端
• 或建造一堵 N-3 大小的墙，并添加到两个大小为 3 的块之一的末端。

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

• 大小为 N-1 的墙的数量（最后有大小为 1 的块）-> T(N-1)
• 加上尺寸为 N-2 的墙的数量，带有 4 个可能的端块（尺寸为 2）-> 4 T(N-2)
• 加上尺寸为 N-3 的墙的数量，带有 2 个可能的端块（尺寸为 3）-> 2 T(N-3)

在那里你得到你的复发。

希望能帮助到你！