Topic describes

Given a positive integer n, find several perfect squares (e.g. 1, 4, 9, 16...). Such that their sum // is equal to n. You want to minimize the number of perfect squares that make up the sum. // Given an integer n, return the minimum number of perfect squares that sum to n. // A perfect square is an integer whose value equals the square of another integer; In other words, its value is equal to the product of a whole // number. For example, 1, 4, 9, and 16 are perfect squares, but 3 and 11 are not.Copy the code

Answer key

// dynamic programming // n must be expressed as: n = a1^2 + A2 ^2 + A3 ^2 +... +an^2 (an^2 <= n) // Let the minimum number of perfect squares of n be f(n). / / / / we know that the number of complete square n including [a1, a2,..., an] (ascending), / / so there must be f (n) = math.h min (f (an) + 1,... , f(a2) + 1, f(a1) + 1. // that is, f(n) is equal to the minimum number of perfect squares of n [a1, A2... an], f(an)... ,f(a2), the minimum of f(a1), plus 1 (assuming the minimum is f(an)). // Add 1 to automatically consider an as one of the perfect squares of n, the complementary perfect square of n. // // Based on the above, we use f(n) = math.min (f(an) + 1... , f (a2) + 1, f (a1) + 1), / / and n ^ 2 = a1 + a2 a3 ^ ^ 2 + 2 +... + an ^ 2 (an ^ 2 < = n) / / can get dp [n] = math.h min (dp [an] + 1,... , dp [a2] + 1, dp [a1] + 1), / / that the dp [n] = Math. Min (dp/n - the I ^ 2 + 1), for (I = 1, the I ^ 2 < = n; Dp [n-i ^2], (for(I = 1; // i^2 <= n; I++)), let us set a for loop, let n go from 1 to n, all state records // into the dynamic programming array dp, so that we can deduce step by step to the desired state dp[n]. // // execution time: 30 ms, beating 87.53% of user // memory consumption in all Java commits: Class Solution {public int numSquares(int n) {int[] dp = new int[n + 1]; for (int i = 1; i <= n; i++) { int temp = Integer.MAX_VALUE; for (int j = 1; j*j <= i; j++) { temp = Math.min(temp, dp[i - j*j] + 1); } dp[i] = temp; } return dp[n]; }}Copy the code