Given an integer n, return the least number of perfect square numbers that sum to n.
A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Q：给定整数n，至少需要多少个完全平方数的和能表示n？

完全平方数即是一些整数的平方，如完全平方数1、4、9、16…分别是整数1、2、3、4…的平方。

Constraints:

  • 1 <= n <= 10^4

Example 1:
**Input:** n = 12
**Output:** 3
**Explanation:** 12 = 4 + 4 + 4.
Example 2:
**Input:** n = 13
**Output:** 2
**Explanation:** 13 = 4 + 9.

解决方法：

动态规划。类似于跳楼梯台阶。
定义一维数组dp，dp[i]表示整数i至少需要dp[i]个正整数表示。

  • 显然dp[0]=0，dp[1]=1；
  • 对应dp[i]，考虑整数i的由完全平方数的组合方式：
    • i = (i-1^2)+1，
    • i = (i-2^2) + 4，
    • i = (i-3^2) + 9，
    • i = (i-4^2) +16，
    • …
    • 也就是说，dp[i]=min(dp[i-k^2])+1，而k=1、2、3、…，只要i-k^2>=0即可

时间复杂度：O(n*sqrt(n))，空间复杂度：O(n)。

实现代码

  1. class Solution {
  2. public:
  3.     int numSquares(int n) {
  4.         vector<int> dp(n+1, 0);
  5.         dp[1] = 1;
  6.         for(int i=2; i<=n; i++){
  7.             int min_dpi = n+1;
  8.             int k=1;
  9.             while(i-k*k >= 0){
  10.                 min_dpi = min(min_dpi, dp[i-k*k]);
  11.                 k++;
  12.             }
  13.             dp[i] = min_dpi + 1;
  14.         }
  15.         return dp[n];
  16.     }
  17. };

运行效率评价

Success Details
Runtime: 98 ms, faster than 71.30% of C++ online submissions for Perfect Squares.
Memory Usage: 9 MB, less than 57.55% of C++ online submissions for Perfect Squares.