#include <limits.h>

#include <cmath>
#include <vector>
class Solution {
public:
    int numSquares(int n) {
        std::vector<int> num_squares(n + 1, INT_MAX);
        num_squares[0] = 0;

        // 遍历所有 sqrt(n) 用来构造平方数
        for (int i = 1; i <= std::sqrt(n); ++i) {
            for (int j = 1; j <= n; j++) {
                // 对每一个大于 i * i 的数，有以下相加组合：
                // a = i * i, b = j - i * i, j = a + b
                // num_squares[j] = num_squares[a] + num_squares[b]
                //                = 1 + num_squares[j]
                if (j - i * i >= 0) {
                    num_squares[j] =
                        std::min(num_squares[j], 1 + num_squares[j - i * i]);
                }
            }
        }
        return num_squares[n];
    }
};