algorithm - 查找数字的所有可能的非连续平方和

Question

问题是这样的:给定一个数字n。找出它可以写成不连续和不重复的平方和的方式的数量。比如n = 117，可以写成3种方式:

1^2 + 4^2 + 6^2 + 8^2 = 117
1^2 + 4^2 + 10^2 = 117
6^2 + 9^2 = 117

我想过用动态规划，用二维表(每个维度都是sqrt(n))但是想不出怎么填表。如果有人可以指导我如何执行此操作或解决此问题的其他方法，我将不胜感激。

Answer 1

把问题当作如何解决这个问题:

我看到两个主要任务:

1. 找到总和为目标的任何正方形序列
2. 测试候选序列的特殊排除是连续的。

您已经知道您不需要测试 x>sqrt(n)。