algorithm - 欧拉计划 #201

Question

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

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

Answer 1

前方剧透!

我想就我如何解决这个问题给出一些提示(并指出它如何适合解决此类问题的一般方法)

提示 1:为以下函数制定(或编写代码)递归

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

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

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

提示 2:制定(或编写代码)函数的递归

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

如果参数数字具有作为总和的 UNIQUE 表示，则函数返回 truenumberOfSquares 二次项的形式 x^2，其中最大 x 小于或等于 maximalIntegerToSquare(递归应该同时涉及函数existsUniqueRepresentation 和 HINT 1 中的函数 existsRepresentation参数值较小)。因此

existsUniqueRepresentation(5,2,2) 返回真，因为 5=2^2+1^2 并且没有其他表示 5 为两个不同的平方 x^2+y^2 x

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

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() 返回的每个值(实际上这在教科书中被称为“记忆化”，动态规划是指一种组织缓存值以便在不进行递归调用的情况下进行计算的方法，但重点始终是缓存子问题的解决方案)。

所以一般的方法是:将问题表述为递归......然后缓存所有移动的东西! (你电脑上有足够内存的所有东西，就是..)

它有效(在这里和许多其他问题中)!