1

我在这个三角形中有大量从 0 到 4 的整数数组。我正在尝试使用 Ruby 学习动态编程，并希望在计算三角形中满足三个标准的路径数方面得到一些帮助：

  1. 您必须从包含 70 个元素的行中的零点之一开始。
  2. 您的路径可以在您正上方的一排（如果正上方有数字）或向左对角线的一排。这些选项之一始终可用
  3. 在第一行达到零的路径总和必须为 140。

例如，从底行的第二个零开始。您可以直接向上移动到 4 的左侧或对角线。在任何一种情况下，您到达的数字都必须添加到您访问过的所有数字的运行计数中。您可以从 1 移动到正上方的 2（运行总和 = 3）或左侧对角线的 0（运行总和 = 1）。

0  
41  
302  
2413  
13024  
024130  
4130241  
30241302  
241302413  
1302413024  
02413024130  
413024130241  
3024130241302  
24130241302413  
130241302413024  
0241302413024130  
41302413024130241  
302413024130241302  
2413024130241302413  
13024130241302413024  
024130241302413024130  
4130241302413024130241  
30241302413024130241302  
241302413024130241302413  
1302413024130241302413024  
02413024130241302413024130  
413024130241302413024130241  
3024130241302413024130241302  
24130241302413024130241302413  
130241302413024130241302413024  
0241302413024130241302413024130  
41302413024130241302413024130241  
302413024130241302413024130241302  
2413024130241302413024130241302413  
13024130241302413024130241302413024  
024130241302413024130241302413024130  
4130241302413024130241302413024130241  
30241302413024130241302413024130241302  
241302413024130241302413024130241302413  
1302413024130241302413024130241302413024  
02413024130241302413024130241302413024130  
413024130241302413024130241302413024130241  
3024130241302413024130241302413024130241302  
24130241302413024130241302413024130241302413  
130241302413024130241302413024130241302413024  
0241302413024130241302413024130241302413024130  
41302413024130241302413024130241302413024130241  
302413024130241302413024130241302413024130241302  
2413024130241302413024130241302413024130241302413  
13024130241302413024130241302413024130241302413024  
024130241302413024130241302413024130241302413024130  
4130241302413024130241302413024130241302413024130241  
30241302413024130241302413024130241302413024130241302  
241302413024130241302413024130241302413024130241302413  
1302413024130241302413024130241302413024130241302413024  
02413024130241302413024130241302413024130241302413024130  
413024130241302413024130241302413024130241302413024130241  
3024130241302413024130241302413024130241302413024130241302  
24130241302413024130241302413024130241302413024130241302413  
130241302413024130241302413024130241302413024130241302413024  
0241302413024130241302413024130241302413024130241302413024130  
41302413024130241302413024130241302413024130241302413024130241  
302413024130241302413024130241302413024130241302413024130241302  
2413024130241302413024130241302413024130241302413024130241302413  
13024130241302413024130241302413024130241302413024130241302413024  
024130241302413024130241302413024130241302413024130241302413024130  
4130241302413024130241302413024130241302413024130241302413024130241  
30241302413024130241302413024130241302413024130241302413024130241302  
241302413024130241302413024130241302413024130241302413024130241302413  
1302413024130241302413024130241302413024130241302413024130241302413024  
02413024130241302413024130241302413024130241302413024130241302413024130
4

1 回答 1

1

但我喜欢家庭作业:)

我发现从顶部开始时更容易推理“路径”问题，反之则遵循规则。

这表示：

  • 部分路径可以是前零，也可以是扩展的部分路径
  • 部分路径 Pr,c 的扩展是，除非 r 是最后一行，它们是完整的，它们的并集
    • Pr,c + P(r+1),c 的扩展
    • Pr,c + P(r+1),c+1 的扩展

“总和”规则只选择所有完整路径中的某些。

于 2009-03-25T21:44:18.443 回答