I think you can make the dp D[i] = { (n, a1, a2, ... , a9) | n <= N }, a list of all the numbers that can be generated with the digits from 1 to i, with the digits they need (for your sample D[9] will contain (345, 0, 1, 0, 0, 0, 0, 2, 0, 3) ) So for each number i from 1 to 10 you have a list of all possible n you can obtain with numbers from 1 to i. We have D[0] = { (0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } For passing from D[i] to D[i + 1], we first set D[i + 1] = D[i], and for each element in D[i + 1] (each pair of 10 numbers), we verify if by adding digit i + 1 we can create a new number, or optimize an existing one.

struct d
{
    int frequence[10]; /// the number of times a digit is neded
    int n;   /// the value of the number obtained with the digits
}

vector <d> DP[10];
DP[0].push_back({ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 });

for (int i = 1; i <= 9; ++i) {
    DP[i] = DP[i - 1];
    for (auto j : DP[i]) {
        /* 
        if by adding the digit i to the number j (so the new value will be j.n + i * i) we obtain a number we do not have who is smaller than N (we don't need the ones bigger), we insert it to DP[i]
        if j.n + i * i is already in DP[i], but the number of needed digits (the sum of frequence[k]) is bigger to the sum of j.freqence[k] + 1, we replace it. If it is equal, we verify in O(10) the better
        */
    }
}

/// now we just have to iterate in DP[9] to see if we have found N.
/// complexity: O(N * 10 * 10)

this works because: — it will calculate all possible numbers — it will only keep the ones with less digits — it will always try to minimise digits

You can solve it with DP by making DP[d][s] = is it possible to make a sum of s with a number of d digits?. The first step is to find the minimum digits that can lead to N. After that, you can perform greedily, assigning the smallest possible digit at each step. I attach code.

#include <bits/stdc++.h>

bool DP[65][5005];
int N;
using namespace std;

int main()
{
    DP[0][0] = true;
    for(int digs = 0; digs < 64; digs++) for(int sum = 0; sum <= 5000; sum++)
    {
        if(!DP[digs][sum]) continue;

        for(int i = 0; i <= 9; i++)
            if((digs > 0 || i > 0) && sum + i*i <= 5000)
                DP[digs+1][sum + i*i] = true;
    }

    cin >> N;
    string ans;

    for(int digs = 1; digs <= 64; digs++) if(DP[digs][N])
    {
        while(digs > 0)
        {
            for(int i = 0; i <= 9; i++)
                if(DP[digs-1][N - i*i])
                {
                    ans += (char) (i + '0');
                    N -= i*i, digs--;
                    break;
                }
        }
    }

    cout << ans;
}

Let's denote dp[i] as the minimum number, which sum of digits' square is i. We can keep it as a string or a BigIntger, which length doesn't exceed 100 (ez to prove).

dp[0] = 0; others are infinity. Consider we are at dp[i]. Now let's iterate over the digits, we will add to the current, say j. Then we update dp[i + j * j] = min(dp[i + j * j], dp[i] * 10 + j)

The answer is dp[N].