1. Perfect squares

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 Explanation: 12 = 4 + 4 + 4. Example 2: Input: n = 13 Output: 2 Description: 13 = 4 + 9.Copy the code
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for (int i = 0; i < n+1; i++) {
            dp[i] = i;
        }
        for (int i = 2; i < n+1; i++) {
            for(int j = 1; j*j <= i; j++) { dp[i] = Math.min(dp[i],dp[i-j*j]+1); }}returndp[n]; }}Copy the code

To be updated…