阿亮的算法之路——279完全平方数

动态规划集中练习

题目详情

自己尝试

因为是动态规划的集中练习，所以第一思路就是用动态规划去做。其实这种后面的会受到前面的影响的题，大都会第一想到动态规划。

这题我想了一会儿，有了大概的思路，
思路就是：
状态转移：当前n的最小次数= 所有可以组成n的两个整数的最小次数的和中最小的

第一次代码

    public static int numSquares(int n ){int [] dp = new int[n+1];for (int i = 1; i <= Math.sqrt(n); i++){ dp[i * i] = 1; }int [] array = new int[n/2];for (int i = 2; i <= n; i++){for (int j = 1; j <= i/2; j++){ array[j-1] = dp[j] +dp[i-j]; }if (dp[i] == 0){dp[i] = array[0];for (int anArray : array){if (anArray != 0 && dp[i] > anArray){ dp[i] = anArray; }}}}return dp[n] ;}

提交结果

可以完成功能，但是有三层for循环，将速度拉得很慢很慢。偶尔一次可以提交通过，很多时候会超时，总是被最后 数很大的用例卡住。

第二次代码

尝试将代码优化，然后将一个数组换成了ArrayList

    public static int numSquares(int n ){int [] dp = new int[n+1];for (int i = 1; i <= Math.sqrt(n);i++ ){ dp[i*i]  = 1; }ArrayList<Integer> array = new ArrayList<>();for (int i = 2; i <= n; i++){for (int j = 1; j <= i/2; j++){ array.add(j-1,dp[j] +dp[i-j]) ; }if (dp[i] == 0){dp[i] = Collections.min(array);array.clear();}}return dp[n] ;}

自己测试也是可以完成功能的，但是提交直接超时。测试总用例588个，第一次还能坚持到最后一个用例，这次才520多个用例就超时了。

说明ArrayList的效率比数组要低，其实想想也是，ArrayList是对数组的封装，如果没有指定初始化容量，当需要的容量大了之后，会进行频繁的数组复制扩容。

第三次代码

        int [] dp = new int[n+1];for (int i = 1; i <= Math.sqrt(n);i++ ){ dp[i*i]  = 1; }int [] array = new int[n/2];for (int i = 2; i <= n; i++){if (dp[i] == 0){dp[i] = dp[1] + dp[i - 1];for (int j = 2; j <= i / 2; j++){ dp[i] = dp[i] > dp[j] + dp[i - j] ? dp[j] + dp[i - j] : dp[i]; }}}return dp[n] ;

进行了优化，少了一层for循环
这次可以稳定通过，但是还是很差，

第四次代码

思考如何能再次优化，在获取最小次数的时候，如果次数是2，那我就直接结束最内层循环，跳到最外层循环，因为次数为1的数，肯定是一些完全平方数，那么剩下的数，是2的肯是最小的了。

    public static int numSquares(int n ){int [] dp = new int[n+1];for (int i = 1; i <= Math.sqrt(n);i++ ){ dp[i*i]  = 1; }int [] array = new int[n/2];a:for (int i = 2; i <= n; i++){if (dp[i] == 0){dp[i] = dp[1] + dp[i - 1];for (int j = i/2; j >=  2; j--){dp[i] = dp[i] > dp[j] + dp[i - j] ? dp[j] + dp[i - j] : dp[i];if (dp[i] == 2){ continue a; }}}}return dp[n] ;

如此一来，效率果然大幅度提升，
比上一次直接提高了两倍，但是还是很差，所有提交通过中最末尾的。

大佬思路

无论我再怎么优化，总是需要几百毫秒，虽然比我一开始有很大的进步，但是水平来看，都是很差的，难道是我的思路不对？？

寻思着大佬是怎么做的，就去看了一下大佬的代码

        int[] dp = new int[n + 1]; // 默认初始化值都为0for (int i = 1; i <= n; i++){dp[i] = i; // 最坏的情况就是每次+1for (int j = 1; i - j * j >= 0; j++){dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程}}return dp[n];

提交结果
果然很优秀，但其实他的思路和我一模一样，但是处理得很巧妙。