项目Euler #201

Question

我已经尝试解决Problem 201有一段时间了，但是我无法为这么大的集合想出一个解决方案。考虑到可能的可达和不超过300,000，我尝试了一个随机算法，但它只适用于具有巨大计算时间的较小集合。然后，我尝试了一种动态编程方法，但没有成功。

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

Answer 1

前面有剧透！

我想就我如何处理这个问题给出几个提示(并指出它如何适用于处理此类问题的一般方法)

提示1:为下面的函数制定(或直接编写代码)递归

布尔型数字(整数，整数maximalIntegerToSquare，整数numberOfSquares)

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

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

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

布尔型数字(整数，整数maximalIntegerToSquare，整数numberOfSquares)

其中，如果参数编号具有唯一的表示形式为x^2的numberOfSquares二次项之和，其中最大x小于或等于maximalIntegerToSquare，则函数返回true (递归应同时涉及提示1中的函数existsUniqueRepresentation和函数existsRepresentation，其中参数的值较小)。因此

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

existsUniqueRepresentation(5,2,3)是假的，因为不存在将5表示为小于或等于2的3个不同数的3个平方和的简单表示(因此没有唯一的表示)(没有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()返回的每个值(实际上，这在教科书中称为“记忆化”，动态编程指的是一种组织缓存的值的方法，以便在不进行递归调用的情况下进行计算，但重点始终是缓存子问题的解决方案)。

因此，一般的方法是:将问题描述为递归。然后缓存所有移动的内容！(您的pc上有足够内存的所有东西，也就是..)

它可以工作(在这里和许多其他问题中)！