再present自然数的平方和使用动态规划

本文介绍了再present自然数的平方和使用动态规划的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

的问题是要找到求和到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); } }