82.完全平方数组成n所需要的最小个数(leetcode279)

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

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

示例 1：

输入：n =12输出：3解释：12 = 4 + 4 + 4

示例 2：

输入：n =13输出：2解释：13 = 4 + 9

int min(int a,int b){ return a<b?a:b; } // 题目限制n最大为10000，定义常量方便修改 #define MAX_NUM 10000 // 全局数组：dp[j]表示组成j的最少完全平方数数量（提前预处理） int f[MAX_NUM + 1]; // 初始化dp数组（仅执行一次，预处理所有结果） void precompute() { // 步骤1：初始化dp数组 // dp[0] = 0（基础条件），其他初始化为INT_MAX（表示"暂时无法组成"） f[0] = 0; for (int j = 1; j <= MAX_NUM; j++) { f[j] = j; } // 步骤2：遍历所有可能的完全平方数（i*i <= 10000 → i最大为100） //一共进行i轮表示从{1},{1,4},{1,4,9}。。选数字，每一轮都更新f数组知道MAXNUM，也就是dp[1]...dp[n]每一轮都被更新 //因为可以选择的完全平方数变多了 for (int i = 1; i * i <= MAX_NUM; i++) { for (int j = i * i; j <= MAX_NUM; j++) { //当前可以选的数字为{1,4,9,...,i*i} //我们已经知道了{1...(i-1)*(i-1)}这些数字组成j的最小数字 //选择i*i，那么当前要组成的数字j需要的数字 = 组成j-i*i所需要的数字+i*i 也就是+1 f[j] = min(f[j], f[j - i * i] + 1); // 不选 vs 选 } } } // 核心函数：查询组成n的最少完全平方数数量 int numSquares(int n) { precompute(); return f[n]; }