The title

Given a positive integer n, find several perfect squares (e.g. 1, 4, 9, 16…). So that their sum is equal to n. You want to minimize the number of perfect squares that make up the sum.

Example 1:

Input: n = 12 Output: 3 Description: 12 = 4 + 4 + 4.Copy the code

Example 2:

Input: n = 13 Output: 2 Description: 13 = 4 + 9.Copy the code

Dynamic programming takes four steps

1. Define state 2. Initial state 3. State transition equation 4Copy the code

Specific to the title

Define state

Define dp[I] as the number of the smallest complete sum of squares of the number I

The initial state

dp[0] = 1 ; dp[1] = 1

State transition equation

Define variable k=1; For the number I, if k+1 is a perfect square and the square of k+1 is I, then dp[I] = 1 and k increases;

Otherwise, iterate through 1 to k, dp[I] = 1+ dp[i-j * j] minimum

if (k + 1) * (k + 1) === i 
   dp[i] = 1;
   k++;
else
   for( j: (1, k ))
    dp[i] = Math.min(1 + dp[i - j * j])
Copy the code

The complete code

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function (n) {
  if (n <= 0) {
    return;
  }
  const dp = [];
  dp[0] = 1;
  dp[1] = 1;
  let k = 1;
  for (let i = 2; i <= n; i++) {
    if ((k + 1) * (k + 1) === i) {
      dp[i] = 1;
      k++;
      continue;
    }
    let min = i;
    for (let j = 1; j <= k; j++) {
      min = Math.min(min, 1 + dp[i - j * j]);
    }
    dp[i] = min;
  }
  console.log(dp);
  return dp[n];
};
Copy the code

conclusion

It’s kind of a simple problem, because the first time you just compare k and k minus 1, you know when you hit 48, k is 6, and the optimal solution is 48=16+16+16, so you can go from 1 to k, and you don’t have to go so much.