😂自顶向下
通常情况下，递归是一种直观而有效的实现算法的方法。 但是，如果我们不明智地使用它，可能会给性能带来一些不希望的损失，例如重复计算。
记忆化（memoization），可以用来避免这个问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int fib(int N) {
f.resize(1000);
fill(f.begin(), f.end(), -1);
f[0] = 0;
f[1] = 1;
return helper(N);
}
int helper(int N)
{
if(f.at(N) != -1)
return f.at(N);
int val = helper(N - 1) + helper(N -2);
f[N] = val;
return val;
}
private:
vector<int> f;
};
|
Accepted
31/31 cases passed (4 ms)
Your runtime beats 74.12 % of cpp submissions
Your memory usage beats 5.01 % of cpp submissions (8.7 MB)
😂自底向上迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int fib(int N) {
f.resize(1000);
fill(f.begin(), f.end(), -1);
f[0] = 0;
f[1] = 1;
return helper(N);
}
int helper(int N)
{
for(int i = 2; i <= N; ++i)
f[i] = f[i - 1] + f[i - 2];
return f[N];
}
private:
vector<int> f;
};
|
Accepted
31/31 cases passed (4 ms)
Your runtime beats 74.12 % of cpp submissions
Your memory usage beats 8.19 % of cpp submissions (8.5 MB)
