问题: https://leetcode-cn.com/problems/perfect-squares/
GitHub 实现:
一, 动态规划实现
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.
往后的情况依次类推
参考:
- 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)
参考:
- 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;
- }
来源: http://www.bubuko.com/infodetail-2979389.html