当前位置：首页 > article >正文

gesp(C++六级)（11）洛谷：P11246：[GESP202409 六级] 小杨和整数拆分

article 2025/2/5 12:02:29

gesp(C++六级)（11）洛谷：P11246：[GESP202409 六级] 小杨和整数拆分

在这里插入图片描述

题目描述

小杨有一个正整数 $n$ ，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。

编程计算总和为 $n$ 的完全平方数的最小数量。

输入格式

输入只有一行一个正整数 $n$ 。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

样例输出 #1

提示

数据规模与约定

对全部的测试数据，保证 $\leq n \leq 10^5$ 。

AC代码（100分）

#include<bits/stdc++.h>
using namespace std;
/*思路： 
	动态规划
	1、dp[i]含义：数字i的最少拆分数量
	2、状态转移方程：dp[i]=min(dp[i],dp[i-j*j]+1);
	   备注1：i-j*j表示i其中一部分被拆成了j*j平方数 
	   备注2：j*j<=i（最大的拆分情况)
*/
int n,a[1010],dp[100010];
int main(){
	cin>>n;
	//dp初始化
	memset(dp,0x3f,sizeof(dp)); //初始化为极大值 
	dp[0]=0; 
	//dp递推 
	for(int i=1;i<=n;i++){//从1枚举到n 
		for(int j=1;j*j<=i;j++){//枚举所有可能的拆分情况 
			dp[i]=min(dp[i],dp[i-j*j]+1);
		}
	} 
	//输出
	cout<<dp[n]; 
	return 0;
}