查找数最短的平方和 [英] Find number's shortest square sum

问题描述

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

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）是最小的硬币（平方数）的数量需要建立你输入号码。

When building your matrix (assuming bottom-up DP), the element denoted in the matrix in D(ceil(sqrt(n)),n) is the minimal number of "coins" (squared numbers) needed to build your input number.

获取是通过跟踪回你的选择在矩阵它建成后进行，并且在每一个点，如果你添加一个加数或不检查实际的元素。
这是更详细的类似问题解释这个线程和的这个线程。

Getting the actual elements is done by tracking back your choices in the matrix after it is built, and at each point checking if you added a summand or not.
This is explained in more details for similar problems in this thread and this thread.

这篇关于查找数最短的平方和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！