【题目描述】
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
给一个正整数 n, 找到若干个完全平方数(比如1, 4, 9, ... )使得他们的和等于 n。你需要让平方数的个数最少。
【题目链接】
www.lintcode.com/en/problem/perfect-squares/
【题目解析】
用一个数组来记录已有的结果，初始化为正无穷(INT_MAX)。外层循环变量i从0到n，内层循环变量j在i的基础上依次加上每个整数的完全平方，超过n的不算。那么i + j*j这个数需要的最少的完全平方数的数量，就是数组中当前的数值，和i位置的数值加上一，这两者之间较小的数字。如果当前的值较小，说明我们已经找到过它需要的完全平方数的个数（最初都是正无穷）。否则的话，说明在i的基础上加上j的平方符合条件，所需的完全平方数的个数就是i需要的个数加上一。
【参考答案】
网友评论