动态规划递归和一点记忆化

StackOverflow https://stackoverflow.com/questions/683511

题

我在这个三角形中有大量从 0 到 4 的整数。我正在尝试使用 Ruby 学习动态编程，并且需要一些帮助来计算三角形中满足三个条件的路径数量：

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

例如，从底行的第二个零开始。您可以直接移动到 1 或 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
有帮助吗？

解决方案

但是我 喜欢 家庭作业 ：）

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

这意味着：

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

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top