将自然数表示为不同方块的总和

Question

问题是找到正整数的最大集合S,使得S的元素的平方和等于给定数量n.

例如:

4 =
2²20
=4²+ 2²38 =5²+3²+
2²300=11²+8²+7²+6²+4²+3²+2²+1².

我有一个及时运行的算法O(2^(sqrt n) * n),但它太慢(每个方块的子集).

Answer 1

O(n^1.5)基于规范动态程序的子集和有一个时间算法.这是重复发生的:

C(m, k) is the size of the largest subset of 1..k whose squares sum to m
C(m, k), m < 0 = -infinity (infeasible)
C(0, k) = 0
C(m, 0), m > 0 = -infinity (infeasible)
C(m, k), m > 0, k > 0 = max(C(m, k-1), C(m - k^2, k-1) + 1)

计算C(m, k)所有min 0..n和all kin 0..floor(n^0.5).返回C(n, floor(n^0.5))目标值.要恢复该集,请追溯argmaxes.