找到数字的最短平方和

Question

查找并输出给定​​数字的最短平方和.

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

输出: {2 2 2}

Answer 1

这是硬币变化的最小硬币变化问题[1,4,9,...,(ceil(sqrt(n)))^2].

可以使用动态编程(DP)通过遵循递推公式来解决:

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(sqrt(n)),n)是构建输入数字所需的最小数量的"硬币"(平方数).

获取实际元素是通过在构建矩阵后跟踪您在矩阵中的选择来完成的,并在每个点检查是否添加了一个加数.
对于此线程和此线程中的类似问题,将更详细地解释这一点.