279. Perfect Squares

class Solution {
    public int numSquares(int n) {
        // 定义 dp[i] 为和为 i 的完全平方数的最小数量
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 最差情况下全部由 1 组成
            for (int j = 2; i - j * j >= 0; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 注意此处是加 1, 因为 j * j 为一个完全平方数
            }
        }

        return dp[n];
    }
}

Reference

279. Perfect Squares