Two beavers live in lodges separated by a large forest.
两只海狸分别住在被大片森林隔开的窝里。
They decide to send messages to each other by shooting fireworks into the sky above the trees.
他们决定通过向树梢上方的天空发射烟花来互相传递信息。
Each message is a sequence of words, though the beavers only know five different words.
每条信息都是一串单词，不过海狸们只认识五个不同的单词。
The beavers can shoot two types of fireworks, one after the other, and know the following codes:
海狸们能够依次发射两种烟花，并且知晓以下代码：
For example, to send the (rather strange) message "food, log, food", a beaver would shoot:
例如，要发送（相当奇怪的）信息“食物，原木，食物”，一只海狸会这样射击：
Question: 问题:
How many different meanings can the following sequence of fireworks have?
下面这一系列烟花能有多少种不同的含义？
Explanation 解释
The correct answer is 4. The message could mean any of the following:
正确答案是 4。该消息可能表示以下任何一种意思：
- log, rock, food, river 日志，岩石，食物，河流
- log, log, log, river 木头，木头，木头，河流
- rock, tree, river 岩石、树木、河流
- rock,food, log, river 岩石、食物、原木、河流
To convince yourself that there are no more possibilities, you can systematically count them:
要让自己确信没有其他可能性，你可以系统地进行计数：
- Start with the first firework. It is not a message, so you can assign a zero to it.
从第一个烟花开始。它不是信息，所以你可以给它赋值为零。
- The first two fireworks can only mean log. Assign number one to the second firework.
前两束烟花只能表示“木”。给第二束烟花标上数字 1。
- We are now at the third firework. It can have a meaning of any shorter sub-sequence plus one new word. Yet we see that there is no way to prolong the previously examined sequences (of length 1 and 2), so we only have one possible meaning (rock) and assign 1 to the third firework.
现在我们来到了第三个烟花。它可以表示任何更短的子序列加上一个新词的意思。然而我们发现无法延长之前考察过的序列（长度为 1 和 2 的），所以我们只有一个可能的意思（“岩石”），于是给第三个烟花赋值 1 。
- The fourth firework is somewhat interesting! It can either add the word log to the first two fireworks, or food to the first three fireworks, as shown by the arrows below. So we sum the two numbers at the 2nd and 3rd firework and assign it to the 4th (1+1=2).
第四个烟花有点意思！它要么把单词“log”加到前两个烟花上，要么把“food”加到前三个烟花上，如下方箭头所示。所以我们把 2 号和 3 号烟花上的两个数字相加，并把这个和赋值给 4 号烟花（1 + 1 = 2）。
- We proceed applying the same idea to each firework to the right. We look one, two and three fireworks back. If those shorter messages can be prolonged with a correct word, we mark this fact with an arrow. Then we just sum the numbers “brought” by the arrows to the currently examined firework.
我们接着将同样的思路应用于右侧的每一个烟花。我们向后看一个、两个和三个烟花。如果那些较短的信息能用一个正确的词加以延长，我们就用箭头标出这一事实。然后，我们只需将箭头“带来”的数字加到当前正在考察的烟花上。
- At the last firework we will have the number of all possible meanings.
在最后一束烟花绽放时，我们将拥有所有可能意义的数量。
The systematic approach when we build our solution systematically step by step and using the previous steps is called dynamic programming. It makes the process much easier.
当我们逐步系统地构建解决方案，并利用之前的步骤时，这种系统的方法被称为动态规划。它使整个过程变得容易得多。
Bebras新赛季备赛已开启，扫码领取Bebras真题资料⇓
欢迎咨询【Bebras专业辅导课程】
（Bebras每日一练部分展示）
