【题目来源】
https://www.luogu.com.cn/problem/P11246
【题目描述】
小杨有一个正整数 n，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。
编程计算总和为 n 的完全平方数的最小数量。
【输入格式】
输入只有一行一个正整数 n。
【输出格式】
输出一行一个整数表示答案。
【输入样例】
18
【输出样例】
2
【数据范围】
对全部的测试数据，保证 1≤n≤10^5。
【算法分析】
● f[i] 表示凑出数字 i 所需要的最少完全平方数个数。
● 初始化 f[i]=i。这是最坏情况，表示全部用 1 去凑数字 i（因为 1 也是完全平方数）。
● 最后一步法的核心思路
我们要凑出数字 i 所需要的最少完全平方数个数，只需关注最后一步加上的那个完全平方数 j²。
既然 i 是由若干完全平方数相加得到，那么它一定可以写成 (i−j²)+j² 的形式，其中 j² 是最后一步加上的平方数；前面 i−j² 这个数所需的最少平方数个数我们已经算出来了，只需要在此基础上再加 1（代表最后这一个平方数），枚举所有合法的 j 并取其中的最小值，就能得到 i 对应的最优解。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int N=1e5+5;
int n,f[N];int main() {cin>>n;for(int i=1; i<=n; i++) {f[i]=i;for(int j=1; j*j<=i; j++) {f[i]=min(f[i-j*j]+1,f[i]);}}cout<<f[n];return 0;
}/*
in:18
out:2
*/
【参考文献】
https://www.luogu.com.cn/problem/solution/P11246