最少的完全平方数

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int numSquares (int n) {
        // write code here
        //↓14-18行可有可无
        for (int i = 1; i < n / 2; i++) {
            if (n == i * i) {
                return 1;
            }
        }

        int[] M = new int[n + 1];
        // M[i] represents the minimum number of boxes to pack num swags up
        // initialize
        M[1] = 1;
        for (int i = 2; i <= n; i++) {
            M[i] = i;
            for (int j = 1; j * j <= i; j++) {
                M[i] = Math.min(M[i - j * j] + 1, M[i]);
            }
        }
        return M[n];
    }
}