小杨和整数拆分

C++ 中等 GESP六级真题 #动态规划#完全平方数

题目描述

题面描述

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

小杨请你编写程序计算出总和为的完全平方数的最少数量。

输入格式

第一行包含一个正整数，含义如题面所示。

输出格式

输出一个整数，代表总和为的完全平方数的最少数量。

样例1

输入：

输出：

样例解释

，其中最少需要2个完全平方数。

数据范围

子任务1：20% 的数据，
子任务2：40% 的数据，
子任务3：40% 的数据，

对于全部数据，保证有。

时间限制

1.0 s

内存限制

512.0 MB

💡 查看提示（先自己想一想再看）

本题考察动态规划的基础应用，定义dp[i]为组成i的最少完全平方数数量，状态转移方程为dp[i] = min(dp[i], dp[i-j*j]+1)，其中j从1遍历到sqrt(i)。初始状态dp[0]=0，dp[i]初始值设为i（最坏情况拆分为i个1相加）。需要注意数组大小要覆盖到1e5的上限，避免越界。

⚙ 开始做这道题 0 人做过 · 0 收藏 · 2 浏览