返回信息流第一种解法:
```
class Solution
{
public:
int numSquares(int n)
{
if (n <= 0)
{
return 0;
}
// cntPerfectSquares[i] = the least number of perfect square numbers
// which sum to i. Note that cntPerfectSquares[0] is 0.
vector<int> cntPerfectSquares(n + 1, INT_MAX);
int count=0;
for(int i=0;i*i<=n;i++)
cntPerfectSquares[i*i]=1;
for (int i = 1; i <= n; i++)
{
// For each i, it must be the sum of some number (i - j*j) and
// a perfect square number (j*j).
for (int j = 1; i+j*j <= n; j++)
{
count++;
cntPerfectSquares[i+j*j] =
min(cntPerfectSquares[i]+1, cntPerfectSquares[i + j*j]);
}
}
cout<<count;
return cntPerfectSquares.back();
}
};
```
耗时66Ms，当n=333333时，count=128133236
第二种解法:
```
class Solution
{
public:
int numSquares(int n)
{
if (n <= 0)
{
return 0;
}
int count=0;
// cntPerfectSquares[i] = the least number of perfect square numbers
// which sum to i. Note that cntPerfectSquares[0] is 0.
vector<int> cntPerfectSquares(n + 1, INT_MAX);
cntPerfectSquares[0] = 0;
for (int i = 1; i <= n; i++)
{
// For each i, it must be the sum of some number (i - j*j) and
// a perfect square number (j*j).
for (int j = 1; j*j <= i; j++)
{
count++;
cntPerfectSquares[i] =
min(cntPerfectSquares[i], cntPerfectSquares[i - j*j] + 1);
}
}
cout<<count;
return cntPerfectSquares.back();
}
};
```
耗时116ms n=333333时，count=128133813
我感觉差不多啊，结果怎么差别这么大呀，而且第一种里面count没算第一个for循环，要是算上就只相差1了。
想问这是为什么？同时想知道时间复杂度怎么算？
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #94731同步于 2018/1/3
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
leetcode 279 perfect square 两种解法动态规划时间差一倍，为
jadfi
2018/1/3镜像同步6 回复
订阅后，新回复会通过你的通知中心匿名送达。
6 条回复
从上面的结果看，单个测试用例的计算次数差别不大，可能测试用例变多了，差别累积就变大了？
【 在 a2013211232 的大作中提到: 】
: 虽然还没看题目，不过我猜这种情况一般都是出现重复计算了，从下至上和从上至下的区别？
【 在 jadfi 的大作中提到: 】
: 第一种解法:
: [md]
: ```
: ...................
把i看成x，用积分算了一下两种方法的循环总次数，不知道能不能解释