[宜信]一个整数可以由若干个整数的平方和表示,求最小划分


一个整数可以由若干个整数的平方和表示,求最小划分。
比如
1 = 1*1,最小划分为1;
2 = 1*1 + 1*1,最小划分为2;
4 = 2*2,最小划分为1;
5 = 2*2 + 1*1,最小划分为2;
给定n,求它的最小划分。
要求尽可能低的时间复杂度。
已邀请:

jefflee

赞同来自: ajianhouyuan


又是DP. 求得1,...N的最小划分后,求N+1, 考虑各种可能性:N+1-1, N+1-2*2, N+1-3*3, ..., N+1-K*K, 直至K*K<=N+1但是(K+1)*(K+1)>N+1. 取其中个数最小的组合。

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~