问题：https://leetcode-cn.com/problems/perfect-squares/
GitHub实现：https://github.com/JonathanZxxxx/LeetCode/blob/master/NumSquares.cs
一、动态规划实现
1、思路：对一个数字n而言，组成的它的完全平方数的最少个数可以根据它减去i*i（这里i*i<n）后对应的那个数的最少完全平方数加一，通过改变i的值最终取得最小值
从简单情况开始
1 1>=1*1 所以1对应等于0对应的最小个数加1,这里0对应的个数为0
2 2>=1*1 所以2对应等于1对应的最小个个数加1，因为之前已经记录了1对应的最小值为1，所以这里最小为2
3 3>=1*1 所以3对应等于2对应的最小个个数加1，因为之前已经记录了2对应的最小值为1，所以这里最小为3
4 4>=1*1和4>=4 所以4对应等于3或者0对应的最小个个数加1，因为之前已经记录了3对应的最小值为3，0对应的最小值为0，所以最终的最小值为1。
往后的情况依次类推
参考：https://blog.csdn.net/zw159357/article/details/82595031
public int NumSquares(int n) { int[] dp = new int[n + 1]; for (int i = 1; i <= n; i++) { dp[i] = n; } for (int i = 1; i <= n; i++) { int j = 1; while (i - j * j >= 0) { dp[i] = Math.Min(dp[i], dp[i - j * j] + 1); j++; } } return dp[n]; }
二、四平方和定理实现
1、思路：任何一个正整数都可以表示成不超过四个整数的平方之和；推论：满足四数平方和定理的数n（四个整数的情况），必定满足 n=4^a(8b+7)
参考：https://blog.csdn.net/lzuacm/article/details/81434270
public int NumSquares2(int n) { while (n % 4 == 0) { n /= 4; } if (n % 8 == 7) { return 4; } for (int i = 0; i * i <= n; i++) { int r = (int)Math.Sqrt(n - i * i); if (i * i + r * r == n) { if (i == 0 || r == 0) return 1; return 2; } } return 3; }
原文：https://www.cnblogs.com/zxxxx/p/10489750.html