解题思路

这是一个完全背包问题的变体：

  1. 问题分析：

    • 目标：找到最少个数的完全平方数，使其和为
    • 每个完全平方数可以重复使用
    • 需要找到所有小于等于 的完全平方数

  2. 动态规划设计：

    • 状态定义： 表示和为 的最少完全平方数个数
    • 初始化：，其他为无穷大
    • 状态转移：
    • 其中 是小于等于 的完全平方数

  3. 优化：

    • 只需要考虑小于等于 的数的平方
    • 使用一维 数组即可

代码

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

int numSquares(int n) {
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;
    
    // 遍历每个数
    for(int i = 1; i <= n; i++) {
        // 遍历每个可能的完全平方数
        for(int j = 1; j * j <= i; j++) {
            dp[i] = min(dp[i], dp[i - j * j] + 1);
        }
    }
    
    return dp[n];
}

int main() {
    int n;
    cin >> n;
    cout << numSquares(n) << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        // 遍历每个数
        for(int i = 1; i <= n; i++) {
            // 遍历每个可能的完全平方数
            for(int j = 1; j * j <= i; j++) {
                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);
        int n = sc.nextInt();
        System.out.println(numSquares(n));
        sc.close();
    }
}

def num_squares(n: int) -> int:
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    
    # 遍历每个数
    for i in range(1, n + 1):
        # 遍历每个可能的完全平方数
        j = 1
        while j * j <= i:
            dp[i] = min(dp[i], dp[i - j * j] + 1)
            j += 1
    
    return dp[n]

if __name__ == "__main__":
    n = int(input())
    print(num_squares(n))

算法及复杂度

  • 算法：动态规划
  • 时间复杂度：，对于每个数 ，需要遍历到
  • 空间复杂度：，需要一个 数组