解题思路: 根据输入的 n 声明一个数组,定义好数组的前两个元素(即第 0 项和第 1 项),从第三个元素开始遍历数组,使数组的每一个元素等于前两个元素之和。最后返回第 n 个元素。
值得注意: 数组的大小应为 n + 1 ,防止数组溢出。
通关代码:
class Solution {
public:
int fib(int n) {
if (n == 0 || n == 1) {
return n;
}
vector<int> arr(n + 1);
arr[0] = 0;
arr[1] = 1;
for (int i = 2; i < n + 1; i++) {
arr[i] = (arr[i - 1] + arr[i - 2]) % 1000000007;
}
return arr[n];
}
};
通关截图: