题解

题面描述

给定一个整数 $n$，要求返回和为 $n$ 的完全平方数的最少数量。
完全平方数 指的是形如 $k^2$ 的数，其中 $k$ 为整数。例如，$1$、$4$、$9$、$16$ 均为完全平方数，而 $3$ 和 $11$ 不是。

思路

本题可以使用动态规划（DP）解决。定义一个数组 $dp$，其中 $dp[i]$ 表示和为 $i$ 的完全平方数的最少数量。

• 状态转移：
  对于每个 $i$，遍历所有满足 $j^2 \le i$ 的 $j$，更新公式为

  $$dp[i] = \min(dp[i],\ dp[i - j^2] + 1)$$

  其中 $dp[i - j^2] + 1$ 表示在和为 $i-j^2$ 的解的基础上再加上一个 $j^2$。

• 初始状态：
  $dp[0] = 0$，表示数字 $0$不需要任何完全平方数的和即可表示。

代码分析

• C++ 实现：
  • 使用一个大小为 $n+1$ 的数组 $dp$，初始时除 $dp[0]$ 外均设为较大值（例如 $INT\_MAX$）。
  • 双重循环：外层遍历 $i$ 从 $1$ 到 $n$，内层遍历所有满足 $j^2 \le i$ 的 $j$。
  • 最后输出 $dp[n]$ 即为答案。

C++

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
using namespace std;

// 使用 Solution 类封装功能函数
class Solution {
public:
    // 函数 numSquares 求解和为 n 的完全平方数的最少数量
    int numSquares(int n) {
        // dp 数组，dp[i] 表示和为 i 的最少完全平方数数量
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0; // 当 i=0 时，数量为 0
        
        // 遍历每个数字 i
        for (int i = 1; i <= n; i++) {
            // 枚举所有可能的完全平方数 j^2
            for (int j = 1; j * j <= i; j++) {
                // 状态转移方程：dp[i] = min(dp[i], dp[i - j^2] + 1)
                dp[i] = min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
};

int main() {
    int n;
    // 输入整数 n
    cin >> n;
    Solution sol;
    // 输出结果
    cout << sol.numSquares(n);
    return 0;
}

Python

# 定义 Solution 类封装功能函数
class Solution:
    # 函数 numSquares 求解和为 n 的完全平方数的最少数量
    def numSquares(self, n: int) -> int:
        # dp 数组，dp[i] 表示和为 i 的最少完全平方数数量
        dp = [float('inf')] * (n + 1)
        dp[0] = 0  # 当 i=0 时，数量为 0
        
        # 遍历每个数字 i
        for i in range(1, n + 1):
            j = 1
            # 枚举所有可能的完全平方数 j^2
            while j * j <= i:
                # 状态转移方程：dp[i] = min(dp[i], dp[i - j^2] + 1)
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1
        return dp[n]

if __name__ == '__main__':
    # 输入整数 n
    n = int(input())
    sol = Solution()
    # 输出结果
    print(sol.numSquares(n))

Java

import java.util.Scanner;

public class Main {
    // 使用 Solution 类封装功能函数，符合 leetcode 风格
    static class Solution {
        // 函数 numSquares 求解和为 $n$ 的完全平方数的最少数量
        public int numSquares(int n) {
            // dp 数组，dp[i] 表示和为 $i$ 的最少完全平方数数量
            int[] dp = new int[n + 1];
            // 初始化 dp 数组，除 dp[0] 外均设为较大值
            for (int i = 1; i <= n; i++) {
                dp[i] = Integer.MAX_VALUE;
                // 枚举所有可能的完全平方数 j^2
                for (int j = 1; j * j <= i; j++) {
                    // 状态转移方程：dp[i] = min(dp[i], dp[i - j^2] + 1)
                    dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
                }
            }
            return dp[n];
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 输入整数 n
        int n = sc.nextInt();
        Solution sol = new Solution();
        // 输出结果
        System.out.println(sol.numSquares(n));
    }
}

Leetcode 279.完全平方数-原题链接

题目内容

给你一个整数 $n$ ，返回 和为 $n$ 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，$1、4、9和 16$ 都是完全平方数，而 $3$和 $11$ 不是。

输入描述

一个整数 $n$

输出描述

一个整数表示和为 $n$ 的完全平方数的最少数量

样例1

输入

12

输出

3

说明

$12 = 4 + 4 + 4$

样例2

输入

13

输出

2

说明

$13 = 4 + 9$

提示：

• $1 <= n <= 10^4$