题目：P11246 [GESP202409 六级] 小杨和整数拆分
题目背景
对应的选择、判断题：https://ti.luogu.com.cn/problemset/1162
题目描述
小杨有一个正整数
n
n
n，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。
编程计算总和为
n
n
n 的完全平方数的最小数量。
输入格式
输入只有一行一个正整数
n
n
n。
输出格式
输出一行一个整数表示答案。
输入输出样例 #1
输入 #1
18
输出 #1
2
说明/提示
数据规模与约定
对全部的测试数据，保证
1
≤
n
≤
10
5
1 \\leq n \\leq 10^5
1≤n≤105。
代码1（朴素版，二维数组，55分）
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,V,v[N],cnt,f[N][N];
bool issquare(int x){
for(int i=1;i<=x/i;i++)
if(i*i==x) return true;
return false;
}
int main(){
cin>>V;
for(int i=1;i<=V;i++)
if(issquare(i)){
cnt++;
v[cnt]=i;
}
n=cnt;
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<=V;j++)
for(int k=0;k*v[i]<=j;k++)
f[i][j]=min(f[i][j],f[i–1][j–k*v[i]]+k);
cout<<f[n][V];
return 0;
}
代码2（优化1，二维数组，80分）
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,V,v[N],cnt,f[N][N];
bool issquare(int x){
for(int i=1;i<=x/i;i++)
if(i*i==x) return true;
return false;
}
int main(){
cin>>V;
for(int i=1;i<=V;i++)
if(issquare(i)){
cnt++;
v[cnt]=i;
}
n=cnt;
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<=V;j++){
f[i][j]=f[i–1][j];
if(v[i]<=j) f[i][j]=min(f[i][j],f[i][j–v[i]]+1);
}
cout<<f[n][V];
return 0;
}
代码3（一维数组，100分）
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,V,v[N],cnt,f[N];
bool issquare(int x){
for(int i=1;i<=x/i;i++)
if(i*i==x) return true;
return false;
}
int main(){
cin>>V;
for(int i=1;i<=V;i++)
if(issquare(i)){
cnt++;
v[cnt]=i;
}
n=cnt;
memset(f,0x3f,sizeof f);
f[0]=0;
for(int i=1;i<=n;i++)
for(int j=v[i];j<=V;j++)
f[j]=min(f[j],f[j–v[i]]+1);
cout<<f[V];
return 0;
}
结果
