查找并输出给定​​数量的最短的平方和。

Find and output the given number's shortest square sum.

例如：12 = 2 ^ 2 + 2 ^ 2 + 2 ^ 2（不是3 ^ 2 + 1 ^ 2 + 1 ^ 2 + 1 ^ 2）

Example: 12 = 2^2 + 2^2 + 2^2 (not 3^2 + 1^2 + 1^2 + 1^2)

输出：{2 2 2}

output: {2 2 2}

推荐答案

这是分硬币变的问题，这里的硬币 [1,4,9，...，（CEIL（开方（N）））^ 2] 。

This is min-coin-change problem, where the coins are [1,4,9,...,(ceil(sqrt(n)))^2].

可以使用动态规划（DP）通过下面的递推公式来解决：

It can be solved using Dynamic Programming (DP) by following the recurrence formula:

D(i,0) = 0
D(i,x) = infinity    x<0
D(0,x) = infinity    x>0
D(i,x) = min { D(i,x-i^2) + 1, D(i-1,x) }

在构建矩阵（假设自下而上DP），表示，在基体中的元素D（CEIL（开方（N）），n）是最小的硬币（平方数）的数量需要建立你输入号码。