algorithm - 欧拉计划 #201

Question

一段时间以来，我一直在尝试解决问题 201，但我无法为这么大的集合提出解决方案。鉴于可能达到的总和不超过 300,000，我尝试了一种随机算法，但它只适用于具有大量计算时间的较小集合。然后我尝试了动态编程方法，但没有成功。

我已经放弃了，但我很好奇如何有效地解决这个问题。

Answer 1

前方剧透！

我想就我如何解决这个问题提供一些提示（并指出它如何以一般方式解决此类问题）

提示 1：制定（或只是编写代码）以下函数的递归

boolean existsRepresentation(int number, int maximalIntegerToSquare, int numberOfSquares)

如果参数 number 的表示形式为 x^2 形式的 numberOfSquares 二次项之和，则函数返回 true，其中最大 x 是 maximalIntegerToSquare。因此

existsRepresentation(5,2,2) 返回 true，因为 5=2^2+1^2 但 existsRepresentation(5,2,3) 为 false，因为没有不同的 x,y,z<=2 使得 5=x^ 2+y^2+z^2

提示 2：制定（或编写代码）函数的递归

boolean existsUniqueRepresentation(int number, int maximalIntegerToSquare, int numberOfSquares)

如果参数 number 具有 UNIQUE 表示形式为 x^2 形式的 numberOfSquares 二次项之和，则函数返回 true，其中最大 x 小于或等于 maximalIntegerToSquare（递归应同时涉及函数 existsUniqueRepresentation 和函数 existsRepresentation来自 HINT 1，参数值较小）。因此

existsUniqueRepresentation(5,2,2) 返回 true 因为 5=2^2+1^2 并且没有其他表示 5 作为两个不同平方 x^2+y^2 x<y 之和的其他表示（最大 y =2 根据需要或其他方式）

existsUniqueRepresentation(5,2,3) 是错误的，因为仅仅因为没有 5 的表示（因此没有唯一表示）作为小于或等于 2 的 3 个不同数字的 3 个平方和（没有 x,y,z其中 1<=x<y<z<=2 ..)

existsUniqueRepresentation(89,8,3) 和 existsUniqueRepresentation(89,9,3) 为假，因为 89=8^2+4^2+3^2 和 89=7^2+6^2+2^2。

您给自己的提示3：使用动态编程，因为您需要缓存existsRepresentation（）或existsUniqueRepresentation（）返回的每个值（实际上这在教科书中称为“记忆化”，动态编程是指一种方式组织缓存的值以便在不进行递归调用的情况下进行计算，但重点始终是缓存子问题的解决方案）。

所以一般的方法是：将问题表述为递归......然后缓存所有移动的东西！（你的电脑上有足够内存的所有东西，也就是说..）

它有效（在这里和许多其他问题）！