问题是找到总和为n所需的最小平方数。
一些例子：
min[ 1] = 1 (1²) min[ 2] = 2 (1² + 1²) min[ 4] = 1 (2²) min[13] = 2 (3² + 2²)
我知道拉格朗日的四平方定理，该定理指出任何自然数都可以表示为四个平方的和。
我正在尝试使用DP解决此问题。
这是我想出的（不正确）
min[i] = 1 where i is a square number min[i] = min(min[i - 1] + 1, 1 + min[i - prev]) where prev is a square number < i
解决此问题的正确DP方法是什么？
我不确定DP是否是解决此问题的最有效方法，但是您要求使用DP。
min [i] = min（min [i-1] +1，1 + min [i-prev]）其中prev是一个平方数 <i 这很接近，我将条件写为
min[i] = min(1 + min[i - prev]) for each square number 'prev <= i'
请注意，i您需要分别检查的不同可能值prev。
i
prev
这是Java的简单实现。
Arrays.fill(min, Integer.MAX_VALUE); min[0] = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j*j <= i; ++j) { min[i] = Math.min(min[i], min[i - j*j] + 1); } }
