solved 'Perfect Squares' on LeetCode https://leetcode.com/problems/perfect-squares/

perfect_square.cc

// Runtime: 200ms. Typical DP.
class Solution {
public:
    int numSquares(int n) {
        vector<int> perfect_records(n + 1, 0);
        
        for (int i = 1; i <= n; ++i) {
            int min_to_perfect = INT_MAX;
            for (int j = 1; i - j * j >= 0; ++j) {
                if (perfect_records[i - j * j] < min_to_perfect) {
                    min_to_perfect = perfect_records[i - j * j];
                }
            }
            perfect_records[i] = min_to_perfect + 1;
        }
        return perfect_records.back();
    }
};