再present自然数的平方和使用动态规划 [英] Represent natural number as sum of squares using dynamic programming

问题描述

的问题是要找到求和到n个所需平方的最小数

The problem is to find the minimum number of squares required to sum to a number n.

一些例子：

min[ 1] = 1 (1²)
min[ 2] = 2 (1² + 1²)
min[ 4] = 1 (2²)
min[13] = 2 (3² + 2²)

我知道的四平方和定理说在任何自然数可以重新psented作为四个平方和$ P $。

I'm aware of Lagrange's four-square theorem that says that any natural number can be represented as the sum of four squares.

我想解决这个使用DP。

I'm trying to solve this using DP.

这就是我想出了（它不是正确的）

This is what I came up with (its not correct)

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的方式来解决这个问题？

What is the correct DP way to solve this?

推荐答案

我不知道，如果DP是解决这一问题的最有效的方式，但你问DP。

分钟[I] = MIN（分[我 - 1] + 1,1 +分[我 - preV]），其中$ P $光伏发电是一个平方数＆LT;我的
这是接近的，我会写的条件为

min[i] = min(min[i - 1] + 1, 1 + min[i - prev]) where prev is a square number < i
This is close, I would write condition as

min[i] = min(1 + min[i - prev]) for each square number 'prev <= i'

请注意，对于每个我您需要检查 $ P $光伏不同的可能值。

Note, that for each i you need to check different possible values of prev.

下面是一个Java简单实现。

Here's simple implementation in 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);
    }
}

这篇关于再present自然数的平方和使用动态规划的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！