Java B组蓝桥杯第十届国赛：平方拆分_蓝桥杯国赛题 平方拆分 动态规划

试题 B: 平方拆分
本题总分：5 分
【问题描述】
将 2019 拆分为若干个两两不同的完全平方数之和，一共有多少种不同的方
法？
注意交换顺序视为同一种方法，例如 13 2 + 25 2 + 35 2 = 2019 与 13 2 + 35 2 +
25 2 = 2019 视为同一种方法。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

尴尬，感谢大佬的指正，我还以为是只要三位平方数，太马虎了。

题目上要若干个，需要利用深度搜索进行统计。

这里值得注意的是，起始位置应该是从1开始，如果从0开始就会造成下列情况：（用题目的例子举例子）

从0开始深度搜索，会得到 ：（ 0 ， 13  ，  25   ， 35） 和（13  ，  25    ， 35）

而从1开始深度搜索，只会得到：（13  ，  25    ， 35）

这两种情况因为没有具体答案，我个人感觉应该第二种，得到的答案：

答案：26287

public class Main {
    int sum; 
	public Main() {
		dfs(2019,1,45);
		System.out.println(sum);
	}
    public void dfs(int num, int min, int max) {
	    if (num < 0) {
	        return;
	    }
	    if (num == 0) {
	        sum ++;
	        return;
	    }
	    for (int i = min; i < max; i++) {
	         dfs(num - i * i, i + 1, max);
	    }
	} 
	public static void main(String[] args) {
		new Main();
	}
}