前言
本篇题解来自洛谷，原作者：MengTian1120，原文：https://www.luogu.com.cn/article/r9kt7c3o。
本篇题解的解题方法为：记忆化搜索。
为什么会没有人写，明明很简单呀。
题目大意
题目十分的简短，没有什么弯弯绕绕的地方。
解题思路
这不是一道搜索吗？
我们定义一个搜索函数，dfs(int x) 它返回 这个数字的最小拆分数量。
退出条件：如果 是完全平方数，那它的最小拆分的数量一定为 。
否则：循环 到 找到最小的dfs(x-i*i)，即 ，并返回 。
#include <bits/stdc++.h>
using namespace std;
int dfs(int x){
if(sqrt(x)==int(sqrt(x))) return 1;
int res=INT_MAX;
for(int i=1;i*i<=x;i++) res=min(res,dfs(x-i*i)+1);
return res;
}
int main(){
int n;
cin>>n;
cout<<dfs(n);
return 0;
}
注意到数据范围，
对全部的测试数据，保证 。
交上去肯定 TLE，这时候我们就可以想到记忆化搜索。
记忆化搜索是一种通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式。
来自 OI-Wiki - https://oi-wiki.org/dp/memo/
开一个 的数组不会 MLE，可以放心使用。
代码实现
于是，我们写出了以下代码。
主要实现方法在注释里。
#include <bits/stdc++.h>
using namespace std;
int f[100005]={};//记录已经计算过的答案，防止重复计算。
int dfs(int x){
if(sqrt(x)==int(sqrt(x))) return 1;//如果是完全平方数，返回1
if(f[x]) return f[x];//如果之前计算过答案，不需要重复计算，直接调用之前计算过的答案
int res=INT_MAX;
for(int i=1;i*i<=x;i++) res=min(res,dfs(x-i*i)+1);
f[x]=res;//记录计算的答案，方便下次调用
return res;
}
int main(){
int n;
cin>>n;
cout<<dfs(n);
return 0;
}
然后提交，AC 了。
AC 代码
#include <bits/stdc++.h>
using namespace std;
int f[100005]={};
int dfs(int x){
if(sqrt(x)==int(sqrt(x))) return 1;
if(f[x]) return f[x];
int res=INT_MAX;
for(int i=1;i*i<=x;i++) res=min(res,dfs(x-i*i)+1);
f[x]=res;
return res;
}
int main(){
int n;
cin>>n;
cout<<dfs(n);
return 0;
}
后记
这是本蒟蒻的第 篇题解，求过。
给个赞再走呗！
Update
- 2026-05-18 修正了部分 Markdown 格式的问题，统一了代码风格。
暂无评论