Find the smallest number of squared integers which sum to N

Given a positive integer n, find the smallest number of squared integers which sum to n.

For example, given n = 13, return 2 since 13 = 3² + 2² = 9 + 4.

Given n = 27, return 3 since 27 = 3² + 3² + 3² = 9 + 9 + 9.

Example:

Input:  n = 13
Output: 2  // 2*2+3*3

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int minPerfectSquareSumN(int num)
{
    int dp[num + 1];

    if (num == 1)
        return 1;
    for (int i = 0; i <= num; i++)
    {
        dp[i] = i;
        for (int j = 1; j * j <= i; j++)
        {
            dp[i] = min(dp[i], 1 + dp[i - j * j]);
        }
    }
    return dp[num];
}
int main()
{
    int num = 13;

    cout << minPerfectSquareSumN(num) << "\n";

    return 0;
}