请解释代码Jam 2009中的算法

Question

这是来自round 1B 2009 Problem C "Square Math"的问题。我知道竞赛分析已经发布了。但是，当一个节点可以被多次访问时，我并不打算讨论如何实现BFS。我只能使用DFS来实现。(因为上下文是隐式保存在递归DFS中的)。如何使用BFS做到这一点？

Answer 1

您必须显式地保存上下文。

对于每个数字单元格，保存一个表，其中包含长度为N的路径在该单元格结束时可以生成的所有合计，以及生成该合计的最佳路径。

对于N=1，此数据很容易生成(每个单元格一个普通路径)，并且给定给定N的表，您可以通过扩展每个路径非常容易地生成下一个大N的表。