我有一个算法问题：我们如何确定一个数是否等于一些不同平方数的和？例如：50=4*4+5*5+3*3
如果这是真的，我怎么能找到状态的数量，我们可以写为几个不同平方的和？
25=5^2+0或3^2+4^2，它有两种状态。
我对2个数字很满意，我知道我们可以用递归来解决它。
这是我用java编写的两个数字的代码：
import java.util.Scanner;
public class SemiCharismatic {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int number = input.nextInt();
input.close();
if (isSquare(number) == true) {
System.out.print("YES");
System.exit(0);
} else {
for (int i = 1; i < number; i++) {
int j = number - i;
if (isSquare(i) == true && isSquare(j) == true) {
System.out.print("YES");
System.exit(0);
}
}
System.out.print("NO");
}
}
static boolean isSquare(int number) {
boolean result = false;
if (Math.sqrt(number) - Math.floor(Math.sqrt(number)) == 0) {
result = true;
}
return result;
}
}
这可以看作是硬币交换问题(请参阅此处(。
解决硬币兑换问题的一种方法是递归的，正如另一种答案所建议的那样：
def is_sum_squared_rec(number, candidates=None, idx=None):
if candidates is None:
candidates = np.arange(1, int(np.floor(np.sqrt(number)))+1) ** 2
idx = len(candidates) - 1
if (number > 0 and idx == -1) or number < 0:
return False
if number == 0:
return True
return is_sum_squared_rec(number, candidates, idx-1) or is_sum_squared_rec(number-candidates[idx], candidates, idx-1)
但在这种情况下，实现硬币交换问题的另一种非递归方法如下：
def is_sum_squared(number):
counts = [1] + [0] * number
candidates = np.arange(1, int(np.floor(np.sqrt(number))) + 1) ** 2
for candidate in candidates:
for jj in range(number, candidate-1, -1):
counts[jj] += counts[jj - candidate]
return counts[number] > 0
这种方法避免了执行冗余计算，并且应该比递归方法更快。
非递归方法可以进一步改进，因为我们不需要整个计数，只要它可以分解为候选的总和。因此，我们可以引入一个提前停止条件：
def is_sum_squared_early_stop(number):
counts = [1] + [0] * number
candidates = np.arange(1, int(np.floor(np.sqrt(number))) + 1) ** 2
for candidate in candidates:
for jj in range(number, candidate-1, -1):
counts[jj] += counts[jj - candidate]
if counts[number] > 0:
return True
return counts[number] > 0
非递归算法的运行时间是O(n*sqrt(n((，而scape要求是O(n(。
时间
对于number = 400，定时产生以下结果：
%timeit is_sum_squared_rec(400)
1.88 ms ± 177 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit is_sum_squared(400)
1.05 ms ± 76.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit is_sum_squared_early_stop(400)
796 µs ± 127 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
几乎是三分之一的改善。当使用number=3000进行检查时，我们得到：
%timeit is_sum_squared_rec(3000)
1.81 s ± 152 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit is_sum_squared(3000)
24.5 ms ± 581 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit is_sum_squared_early_stop(3000)
14.3 ms ± 556 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
我们有超过2个数量级的差异
这个问题是子集和问题的一个变体。
在这里，你必须创建一组你自己的(下面解释(，你的数字是问题的目标和。
要创建一个集合，请形成一个数字数组[square of numbers from {1 to sqrt(n)}]
因此，您的阵列将看起来像：[1,4,9... sqrt(n)^2]
解释为什么sqrt(n(：任何大于sqrt(n(的数的平方也将大于n。因此，向其添加更多不会得到解决方案。
然后应用子集集算法，如这里所解释的
isSubsetSum(set, n, sum)
= isSubsetSum(set, n-1, sum) || isSubsetSum(set, n-1, sum-set[n-1])
Base Cases:
isSubsetSum(set, n, sum) = false, if sum > 0 and n == 0
isSubsetSum(set, n, sum) = true, if sum == 0