279. Complete square

279. Complete square

Give you an integer n , return And for n The minimum number of complete squares of .

Complete square It's an integer , Its value is equal to the square of another integer ; let me put it another way , Its value is equal to the product of the self multiplication of an integer . for example ,1、4、9 and 16 They're all perfect squares , and 3 and 11 No .

Example 1：

Input ：n = 12
Output ：3
explain ：12 = 4 + 4 + 4

Example 2：

Input ：n = 13
Output ：2
explain ：13 = 4 + 9
We can write the state expression according to the requirements of the topic ：f[i]f[i]f[i] Represents the minimum number of squares needed to represent an integer iii.

These numbers must fall in the interval [1,n] [1,sqrt{n}][1,n​]. We can enumerate these numbers , Suppose the current enumeration goes to jjj, Then we need to take the square of some numbers , constitute i−j2i-j^2i−j2. At this point, we find that the subproblem is similar to the original problem , It's just getting smaller . This meets the requirements of dynamic programming , So we can write the state transition equation .

For this question , In fact, we use the idea of dynamic programming , Or search from the beginning , about , Every number , We get its complete square number from scratch , Then add up one by one , Add to n, This allows for all combinations , The solution code is as follows ：

int numSquares(int n){
    
    int dp[n+1];
  
  int i,j;
  dp[0]=0;
  for(i=1;i<=n;i++){
    
      dp[i]=INT_MAX;
      for(j=1;j<=sqrt(i);j++){
    
          dp[i]=fmin(dp[i],dp[i-j*j]+1);
      }
  // printf("i %d -%d ",i,dp[i]);
  }

  return dp[n];
   

}