完全平方数

题目要求

这个问题是一个经典的动态规划问题，要求解的是给定一个整数n，找出使得它们的和等于n的完全平方数的最小数量。完全平方数是指可以表示为某个整数的平方的数，例如 1（=1x1）、4（=2x2）、9（=3x3）等等。

解题思路

为了解决这个问题，我们可以采用动态规划的方法。动态规划是一种将复杂问题分解成更小的子问题来解决的方法，并且存储子问题的解，避免重复计算。

初始化动态规划数组：创建一个数组dp，其中dp[i]表示和为i的完全平方数的最小数量。数组的大小为n+1，初始时，除了dp[0]为 0 以外，其余的dp[i]都设置为一个大于n的数，因为和为i的完全平方数的数量不可能大于n。
预处理完全平方数：计算出所有小于等于n的完全平方数，并存储在一个列表中，这样我们就可以在后续的计算中直接使用这些数。
填充动态规划数组：对于数组dp中的每个元素dp[i]（i从 1 到n），我们遍历所有的完全平方数square，对于每个square，如果square小于等于i，我们就计算dp[i - square] + 1的值，并更新dp[i]为当前的dp[i]和dp[i - square] + 1中的较小值。这里+1表示加上这个完全平方数square。
找到结果：经过上述步骤，dp[n]中存储的就是和为n的完全平方数的最小数量。

这个动态规划的过程基本上是在尝试将n分解为若干个完全平方数的和，并且在这个过程中尽可能地使用较少的完全平方数。通过比较所有可能的分解方法，我们可以找到最优的解。

Golang 版本

package main

import (
	"fmt"
	"math"
)

func numSquares(n int) int {
	// 初始化dp数组，初始值设为一个比n大的数，这里用n+1
	dp := make([]int, n+1)
	for i := range dp {
		dp[i] = n + 1
	}
	// base case
	dp[0] = 0

	// 预处理所有可能的完全平方数
	maxSquareIndex := int(math.Sqrt(float64(n))) + 1
	squares := make([]int, maxSquareIndex)
	for i := 1; i < maxSquareIndex; i++ {
		squares[i] = i * i
	}

	// 动态规划填充dp数组
	for i := 1; i <= n; i++ {
		for _, square := range squares {
			if square <= i {
				dp[i] = min(dp[i], dp[i-square]+1)
			}
		}
	}

	return dp[n]
}

// 辅助函数，返回两个整数中较小的一个
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	n := 12 // 示例
	fmt.Println("The least number of perfect squares is:", numSquares(n))
}

这段代码定义了一个numSquares函数，它接受一个整数n，并返回和为n的完全平方数的最少数量。在main函数中，我们给出了一个示例，调用numSquares函数并打印结果。

C++版本

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>

int numSquares(int n) {
    std::vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;

    // 预处理所有可能的完全平方数
    int maxSquareIndex = std::sqrt(n) + 1;
    std::vector<int> squares(maxSquareIndex);
    for (int i = 1; i < maxSquareIndex; ++i) {
        squares[i] = i * i;
    }

    // 动态规划填充dp数组
    for (int i = 1; i <= n; ++i) {
        for (int s = 1; s < maxSquareIndex; ++s) {
            if (squares[s] <= i) {
                dp[i] = std::min(dp[i], dp[i - squares[s]] + 1);
            }
        }
    }

    return dp[n];
}

int main() {
    int n = 12; // 示例
    std::cout << "The least number of perfect squares is: " << numSquares(n) << std::endl;
    return 0;
}

这段 C++代码实现了与 Golang 版本相同的功能。它定义了一个numSquares函数，用于计算和为n的完全平方数的最少数量。在main函数中，我们设置了一个示例值n = 12，调用numSquares函数，并输出结果。

Python 版本

import math

def numSquares(n):
    # 初始化dp数组，初始值设为无穷大
    dp = [float('inf')] * (n + 1)
    # base case
    dp[0] = 0

    # 预处理所有可能的完全平方数
    max_square_index = int(math.sqrt(n)) + 1
    squares = [i**2 for i in range(1, max_square_index)]

    # 动态规划填充dp数组
    for i in range(1, n + 1):
        for square in squares:
            if i >= square:
                dp[i] = min(dp[i], dp[i - square] + 1)

    return dp[n]

# 示例
n = 12
print("The least number of perfect squares is:", numSquares(n))

这段 Python 代码实现了一个numSquares函数，它接受一个整数n作为输入，并返回和为n的完全平方数的最少数量。在代码的最后，我们给出了一个示例，调用numSquares函数并打印结果。

Java 版本

public class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        // 初始化dp数组，初始值设为最大整数
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        // base case
        dp[0] = 0;

        // 计算所有小于等于n的完全平方数
        int maxSquareIndex = (int) Math.sqrt(n) + 1;
        int[] squares = new int[maxSquareIndex];
        for (int i = 1; i < maxSquareIndex; i++) {
            squares[i] = i * i;
        }

        // 动态规划求解
        for (int i = 1; i <= n; i++) {
            for (int s = 1; s < maxSquareIndex; s++) {
                if (i >= squares[s]) {
                    dp[i] = Math.min(dp[i], dp[i - squares[s]] + 1);
                }
            }
        }

        return dp[n];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 12;
        System.out.println("The least number of perfect squares is: " + solution.numSquares(n));
    }
}

这段 Java 代码定义了一个Solution类，其中包含了numSquares方法，用于计算和为n的完全平方数的最少数量。在main方法中，我们创建了一个Solution对象，并调用numSquares方法，然后打印出结果。

Rust 版本

use std::cmp::min;
use std::f64;

fn num_squares(n: i32) -> i32 {
    let mut dp = vec![i32::MAX; (n + 1) as usize];
    dp[0] = 0;

    for i in 1..=n as usize {
        let mut j = 1;
        while j * j <= i {
            dp[i] = min(dp[i], dp[i - j * j] + 1);
            j += 1;
        }
    }

    dp[n as usize]
}

fn main() {
    let n = 12;
    println!("The least number of perfect squares is: {}", num_squares(n));
}

这段 Rust 代码实现了一个num_squares函数，它接受一个整数n作为输入，并返回和为n的完全平方数的最少数量。在main函数中，我们设置了一个示例值n = 12，调用num_squares函数，并打印出结果。

总结

上述问题的解法涉及到了动态规划（Dynamic Programming, DP）的思想。核心思路是创建一个数组dp，其中dp[i]表示组成和为i的完全平方数的最小数量。解法的步骤如下：

初始化一个数组dp，大小为n+1，并将除了dp[0]之外的所有元素设为一个大于n的数，因为最坏情况下，和为i的完全平方数的数量不会超过i（即i个 1 的平方和）。
设置dp[0]的值为 0，因为和为 0 的完全平方数的最小数量显然是 0。
预处理所有小于等于n的完全平方数，并存储在一个列表或数组中，以便后续快速查找。
使用两层循环来填充dp数组。外层循环遍历从 1 到n的每个数i，内层循环遍历所有的完全平方数。对于每个i和完全平方数square，如果square小于等于i，则更新dp[i]为dp[i]和dp[i - square] + 1中的较小值。
最终，dp[n]中存储的就是和为n的完全平方数的最小数量。

这个问题的解法在不同的编程语言中都是类似的，只是语法和一些细节上有所不同。在上面的回答中，我们提供了 Golang、C++、Python、Java 和 Rust 版本的代码实现。每种语言都遵循了动态规划的基本步骤，但是在数组初始化、循环结构和语言特定的函数调用等方面有所区别。

hot-100