本文共 1174 字，大约阅读时间需要 3 分钟。

问题描述：给定一个正整数n，我们需要找到若干个完全平方数，使它们的和等于n，并使得到达和的完全平方数的个数最少。例如，n=12时，可以是4+4+4，总共有3个平方数。

提示：完全平方数是指某个整数的平方，例如1,4,9,16等。给定n的取值范围是在1到104之间。

解题思路：这次问题可以使用动态规划技术来解决。动态规划是一种通过重用中间计算结果来高效地解决问题的方法。我们可以将问题分解为更小的子问题，并保存已经计算出的子问题的解，以便快速解决当前问题。

关键点：

代码实现：

public class Solution {    public int numSquares(int n) {        int dp[] = new int[n + 1];        for (int i = 1; i <= n; i++) {            dp[i] = i; // 最坏情况下，每个数都是1            for (int j = 0; i - j * j >= 0; j++) {                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);            }        }        return dp[n];    }}

解释：

• 初始化：dp数组从1到n初始化为i，这是因为在没有找到更优解的情况下，我们假设需要i个1。

• 动态转移：对于每个i，从1到n，我们检查从i开始减去j²（j从0开始，j大的平方数尽量大），更新dp[i]为当前最小的平方数个数。每次尝试减去一个平方数后，剩余部分i-j²的值已经在dp中计算过，因此可以快速得到解。

• 高效性：通过递归地减少问题规模，我们避免了递归可能带来的堆栈溢出问题，并且能够显著减少计算量。每个数字i只需要检查到sqrt(i)的平方数j²，时间复杂度为O(n√n)，在n=104的情况下非常高效。

• 结果：dp[n]将包含由最少完全平方数之和等于n的个数。

该方法利用动态规划技术有效地解决了问题，最少平方数之和的问题得到了优化，并通过示例验证了其准确性和效率。

转载地址：http://uegyk.baihongyu.com/