algorithm - 请从 Code Jam 2009 解释这个算法

Question

这是2009 年第 1B 轮问题 C“平方数学”中的问题。我知道比赛分析已发布。但是当一个节点可以被多次访问时，我并没有讨论如何实现 BFS。我只能使用 DFS 来实现。（因为上下文隐式保存在递归 DFS 中）。如何使用 BFS 做到这一点？

Answer 1

您必须明确保存上下文。

对于每个数字单元格，保留一个表格，其中列出了可以通过在该单元格处结束的长度为 N 的路径产生的所有总计，以及对于每个总计，产生它的最佳路径。

对于 N = 1，此数据很容易生成（每个单元格有一个简单的路径）并且给定给定 N 的表格，您可以通过扩展每条路径很容易地为下一个更大的 N 生成表格。