A30362. 小杨和整数拆分
填空题
困难
知识点
题目描述
小杨和整数拆分
题目描述
小杨有一个正整数 n，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。
小杨请你编写程序计算出总和为 n 的完全平方数的最少数量。
输入格式
第一行包含一个正整数 n，含义如题目所示。
输出格式
输出一个整数，代表总和为 n 的完全平方数的最少数量。
输入样例
18
输出样例
2
18=9+9=16+1+1，其中最少需要2个完全平方数。
对于全部数据，保证有 1≤n≤100000。
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n;
int dp[N];
int main() {
cin>>n;
for (int i=1;i<=n;i++) {
dp[i]=i;
for (int j=1;j<=sqrt(i);j++) {
dp[i] =min(dp[i-j*j]+1,dp[i]);
}
}
cout<<dp[n]<<"\n";
}
上一题
下一题